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