· KLDP.org · KLDP.net · KLDP Wiki · KLDP BBS ·
Linuxdoc Sgml/tiger_in_Lex_yacc

You are not allowed to 'edit'


tiger language parser

tiger language parser

ÀÌ Çüä hclee80 atat gmail dotdot com

ÃÖÃʼöÁ¤ÀÏ : 2008³â 06¿ù 18ÀÏ ( ¼ö¿äÀÏ, ºñ )

ÃÖÁ¾¼öÁ¤ÀÏ : 2008³â 06¿ù 19ÀÏ ( ¸ñ¿äÀÏ, È帲 )


Tiger is derived from a language introduced by Andrew Appel in his book Modern Compiler Implementation.

sgmlºÎÅÍ ¹è¿ö¾ß°Ú³×¿ä. ±×·¯°íº¸´Ï Ã¥µµ ¾ø³×¿ä. »ç¿ë¹ýÀÌ ¾î·Æ³×.

1. tiger? Mac? woods?

ŸÀÌ°Å( tiger ) ¾ð¾î. MacÀÇ OSµµ ¾Æ´Ï°í, ŸÀÌ°Å¿ìÁîµµ ¾Æ´Õ´Ï´Ù.. ¾Øµå·ù ¾ÖÆÞ±³¼ö(Ä·ºê¸®Áö´ëÇÐ)ÀÇ ¸ð´ø ÄÄÆÄÀÏ·¯ Á¦ÀÛÀ̶õ Ã¥( Àϸí:ŸÀÌ°ÅºÏ )À» ¹ÙÅÁÀ¸·Î Çлý ÇÁ·ÎÁ§Æ®¼ºÀ¸·Î ¸¸µé¾îÁø ¾ð¾îÀÔ´Ï´Ù. 

2. lex & yacc | flex & bison | etc


2.1 lex & yacc


2.2 flex & bison


2.3 etc


3. tiger vs tinyC vs C-minus


3.1 tinyC


tinyC ( ŸÀÌ´Ï ¾¾(0) ), compiler construction, principles and practice -> kenneth C, rouden ( ÄÄÆÄÀÏ·¯ Á¦ÀÛ, ¿ø¸®¿Í ½ÇÁ¦ -> ±èÀçÈÆ|µµ°æ±¸|¿ì±Õ|Á¤´ö±æ|Á¤¹Î¼ö)ÀÌ ¾ø´Ù.
Ã¥¿¡¼­ ÄÄÆÄÀÏ·¯ÀÇ ½ºÄ³³Ê & Æļ­ ( front-end ) ¼³¸íÀ» À§Çؼ­ ¾²¿©Áø °£´ÜÇÑ ¾ð¾îÀÌ´Ù. ¿µ¾î¸¦ ±×´ë·Î Çؼ®Çصµ ÁÁÀ» µíÇÏ´Ù.

¾Æ½±°Ôµµ ÀÌ Ã¥¿¡¼­´Â ÄÄÆÄÀÏ·¯Ã¥ ƯÀ¯ÀÇ º°Äª( µå·¡°ïºÏ,ŸÀÌ°ÅºÏ )ÀÌ ¾ø´Ù. ÃâÆÇÇÒ¶§ µ¿¹°Çϳª¸é ³ÖÀ¸¸é µÉ°ÍÀ»...°³ÀÎÀûÀ¸·Î ¸¾¸ð½º¸¦ ÃßõÇÑ´Ù.

4. C-minus


5. tiger


6. tiger lexical


Keywords
¡®array¡¯, ¡®if¡¯, ¡®then¡¯, ¡®else¡¯, ¡®while¡¯, ¡®for¡¯, ¡®to¡¯, ¡®do¡¯, ¡®let¡¯, ¡®in¡¯, ¡®end¡¯, 
¡®of¡¯, ¡®break¡¯, ¡®nil¡¯, ¡®function¡¯, ¡®var¡¯, ¡®type¡¯, ¡®import¡¯ and ¡®primitive¡¯ 

Object-related keywords
The keywords ¡®class¡¯, ¡®extends¡¯, ¡®method¡¯ and ¡®new¡¯ are reserved for object-related constructions. 
They are valid keywords when the object extension of the language is enabled, 
and reserved words if this extension is disabled (i.e., they cannot be used as identifiers in object-less syntax). 

Symbols
¡®,¡¯, ¡®:¡¯, ¡®;¡¯, ¡®(¡¯, ¡®)¡¯, ¡®[¡¯, ¡®]¡¯, ¡®{¡¯, ¡®}¡¯, ¡®.¡¯, ¡®+¡¯, ¡®-¡¯, ¡®*¡¯, ¡®/¡¯, 
¡®=¡¯, ¡®<>¡¯, ¡®<¡¯, ¡®<=¡¯, ¡®>¡¯, ¡®>=¡¯, ¡®&¡¯, ¡®|¡¯, and ¡®:=¡¯ 

White characters
Space and tabulations are the only white space characters supported. Both count as a single character when tracking locations. 

End-of-line
End of lines are ¡®\n\r¡¯, and ¡®\r\n¡¯, and ¡®\r¡¯, and ¡®\n¡¯, freely intermixed. 

Strings
The strings are ANSI-C strings: enclosed by ¡®"¡¯, with support for the following escapes: 
¡®\a¡¯, ¡®\b¡¯, ¡®\f¡¯, ¡®\n¡¯, ¡®\r¡¯, ¡®\t¡¯, ¡®\v¡¯
control characters. 

\num
The character which code is num in octal. num is composed of exactly three octal characters, and any invalid value is a scan error. 

\xnum
The character which code is num in hexadecimal (upper case or lower case or mixed). num is composed of exactly 2 hexadecimal characters. 

¡®\\¡¯
A single backslash. 

¡®\"¡¯
A double quote. 

\character
If no rule above applies, this is an error. 

All the other characters are plain characters and are to be included in the string. In particular, multi-line strings are allowed. 

Comments
Like C comments, but can be nested: 

          Code
          /* Comment
             /* Nested comment */
             Comment */
          Code

Identifiers
Identifiers start with a letter, followed by any number of alphanumeric characters plus the underscore. Identifiers are case sensitive.
Moreover, the special _main string is also accepted as a valid identifier. 

          id ::= letter { letter | digit | _ } | _main
          letter ::=
              a | b | c | d | e | f | g | h | i | j | k | l |
              m | n | o | p | q | r | s | t | u | v | w | x |
              y | z |
              A | B | C | D | E | F | G | H | I | J | K | L |
              M | N | O | P | Q | R | S | T | U | V | W | X |
              Y | Z
          digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Numbers
There are only integers in Tiger. 

          integer ::= digit { digit }
          op ::= + | - | * | / | = | <> | > | < | >= | <= | & | |
     
Invalid characters
Any other character is invalid.

6.1 tiger.l - lex


7. tiger EBNF

We use Extended BNF, with ¡®[¡¯ and ¡®]¡¯ for zero or once, and ¡®{¡¯ and ¡®}¡¯ for any number of repetition including zero. 

     program ::=
         exp
       | decs
     
     exp ::=
       # Literals.
         nil
       | integer
       | string
     
       # Array and record creations.
       | type-id [ exp ] of exp
       | type-id {[ id = exp { , id = exp } ] }
     
       # Object creation.
       | new type-id
     
       # Variables, field, elements of an array.
       | lvalue
     
       # Function call.
       | id ( [ exp { , exp }] )
     
       # Method call.
       | lvalue . id ( [ exp { , exp }] )
     
       # Operations.
       | - exp
       | exp op exp
       | ( exps )
     
       # Assignment.
       | lvalue := exp
     
       # Control structures.
       | if exp then exp [else exp]
       | while exp do exp
       | for id := exp to exp do exp
       | break
       | let decs in exps end
     
     lvalue ::= id
       | lvalue . id
       | lvalue [ exp ]
     exps ::= [ exp { ; exp } ]
     
     decs ::= { dec }
     dec ::=
       # Type declaration.
        type id = ty
       # Class declaration (alternative form).
       | class id [ extends type-id ] { classfields }
       # Variable declaration.
       | vardec
       # Function declaration.
       | function id ( tyfields ) [ : type-id ] = exp
       # Primitive declaration.
       | primitive id ( tyfields ) [ : type-id ]
       # Importing a set of declarations.
       | import string
     
     vardec ::= var id [ : type-id ] := exp
     
     classfields ::= { classfield }
     # Class fields.
     classfield ::=
       # Attribute declaration.
         vardec
       # Method declaration.
       | method id ( tyfields ) [ : type-id ] = exp
     
     # Types.
     ty ::=
        # Type alias.
          type-id
        # Record type definition.
        | { tyfields  }
        # Array type definition.
        | array of type-id
        # Class definition (canonical form).
        | class [ extends type-id ] { classfields }
     tyfields ::= [ id : type-id { , id : type-id } ]
     type-id ::= id
     
     op ::= + | - | * | / | = | <> | > | < | >= | <= | & | |

Precedence of the op (high to low): 

     * /
     + -
     >= <= = <> < >
     &
     |

Comparison operators (<, <=, =, <>, >, >=) are not associative. All the remaining operators are left-associative. 

8. tiger BNF

8.1 tiger.y - yacc

9. URL

  • â½ÃÀÚ : http://www.cs.princeton.edu/~appel/
  • ref : http://www.lrde.epita.fr/~akim/ccmp/tiger.html
  • ref : http://www.program-transformation.org/Tiger/TigerLanguage
  • ref : http://www.eecs.harvard.edu/ govereau/tigerc/tiger-slides.pdf
  • ref : http://www.cs.princeton.edu/ appel/modern/c/

10. Âü°íµµ¼­

  • lex & yacc - O'Reilly & Associates. Inc.


ID
Password
Join
Preserve the old, but know the new.


sponsored by andamiro
sponsored by cdnetworks
sponsored by HP

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2008-06-19 18:14:08
Processing time 0.0015 sec