ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Implementing a Simple Interpreter

?
?
Ray Song
Ray Song

The document describes the process of implementing a simple interpreter, including lexical analysis to tokenize code into tokens, grammatical analysis to parse code according to a grammar using techniques like recursive descent parsing, and evaluating expressions using algorithms like the shunting-yard or abstract syntax trees. It provides examples of grammars and implementation details to parse statements, expressions, conditionals, loops, and handle indentation.

1 of 71
Downloaded 12 times
Implementing a Simple Interpreter Ray Song May 27, 2012 Ray Song Implementing a Simple Interpreter
Flow sheet Lexical analysis Grammatical analysis Figure : Flow Ray Song Implementing a Simple Interpreter
Flow sheet Lexical analysis Grammatical analysis Figure : Flow Ray Song Implementing a Simple Interpreter
Lexical Analysis manual ?ex Ray Song Implementing a Simple Interpreter
Lexical Analysis manual ?ex Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
Tokens identi?er integer string while if else print NEWLINE NO WHITESPACE Ray Song Implementing a Simple Interpreter
O?-side rule def hello(): print ¡®world¡¯ indentation sensitive Ex: ISWIM(1966), occam(1983), Miranda(1985), Haskell(1990), Python(1991) Ray Song Implementing a Simple Interpreter
O?-side rule def hello(): print ¡®world¡¯ indentation sensitive Ex: ISWIM(1966), occam(1983), Miranda(1985), Haskell(1990), Python(1991) Ray Song Implementing a Simple Interpreter
O?-side rule - Cont. represented as virtual tokens INDENT DEDENT Ray Song Implementing a Simple Interpreter
O?-side rule - Cont. represented as virtual tokens INDENT DEDENT Ray Song Implementing a Simple Interpreter
O?-side rule - Cont. represented as virtual tokens INDENT DEDENT Ray Song Implementing a Simple Interpreter
Example if a > 2: print 5 print a IF a > 2 : NEWLINE INDENT PRINT 5 NEWLINE DEDENT PRINT a NEWLINE Ray Song Implementing a Simple Interpreter
Grammatical analysis Cocke¨CYounger¨CKasami algorithm Earley¡¯s algorithm LR parser Recursive-descent parser Ray Song Implementing a Simple Interpreter
Grammatical analysis Cocke¨CYounger¨CKasami algorithm Earley¡¯s algorithm LR parser Recursive-descent parser Ray Song Implementing a Simple Interpreter
Grammatical analysis Cocke¨CYounger¨CKasami algorithm Earley¡¯s algorithm LR parser Recursive-descent parser Ray Song Implementing a Simple Interpreter
Grammatical analysis Cocke¨CYounger¨CKasami algorithm Earley¡¯s algorithm LR parser Recursive-descent parser Ray Song Implementing a Simple Interpreter
Tools Bison Can generate C, C++ and Java codes ANTLR Ray Song Implementing a Simple Interpreter
Tools Bison Can generate C, C++ and Java codes ANTLR Ray Song Implementing a Simple Interpreter
Tools Bison Can generate C, C++ and Java codes ANTLR Ray Song Implementing a Simple Interpreter
Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
Parser combinator Straightforward to construct Readability Parsec Ray Song Implementing a Simple Interpreter
Parser combinator Straightforward to construct Readability Parsec Ray Song Implementing a Simple Interpreter
Parser combinator Straightforward to construct Readability Parsec Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
Example if a > 2: print 5 print a Ray Song Implementing a Simple Interpreter
Example - Cont. Figure : Parse Ray Song Implementing a Simple Interpreter
Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter
Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter
Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter
Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter
Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter

More Related Content

Implementing a Simple Interpreter

  • 1. Implementing a Simple Interpreter Ray Song May 27, 2012 Ray Song Implementing a Simple Interpreter
  • 2. Flow sheet Lexical analysis Grammatical analysis Figure : Flow Ray Song Implementing a Simple Interpreter
  • 3. Flow sheet Lexical analysis Grammatical analysis Figure : Flow Ray Song Implementing a Simple Interpreter
  • 15. O?-side rule def hello(): print ¡®world¡¯ indentation sensitive Ex: ISWIM(1966), occam(1983), Miranda(1985), Haskell(1990), Python(1991) Ray Song Implementing a Simple Interpreter
  • 16. O?-side rule def hello(): print ¡®world¡¯ indentation sensitive Ex: ISWIM(1966), occam(1983), Miranda(1985), Haskell(1990), Python(1991) Ray Song Implementing a Simple Interpreter
  • 17. O?-side rule - Cont. represented as virtual tokens INDENT DEDENT Ray Song Implementing a Simple Interpreter
  • 18. O?-side rule - Cont. represented as virtual tokens INDENT DEDENT Ray Song Implementing a Simple Interpreter
  • 19. O?-side rule - Cont. represented as virtual tokens INDENT DEDENT Ray Song Implementing a Simple Interpreter
  • 20. Example if a > 2: print 5 print a IF a > 2 : NEWLINE INDENT PRINT 5 NEWLINE DEDENT PRINT a NEWLINE Ray Song Implementing a Simple Interpreter
  • 21. Grammatical analysis Cocke¨CYounger¨CKasami algorithm Earley¡¯s algorithm LR parser Recursive-descent parser Ray Song Implementing a Simple Interpreter
  • 22. Grammatical analysis Cocke¨CYounger¨CKasami algorithm Earley¡¯s algorithm LR parser Recursive-descent parser Ray Song Implementing a Simple Interpreter
  • 23. Grammatical analysis Cocke¨CYounger¨CKasami algorithm Earley¡¯s algorithm LR parser Recursive-descent parser Ray Song Implementing a Simple Interpreter
  • 24. Grammatical analysis Cocke¨CYounger¨CKasami algorithm Earley¡¯s algorithm LR parser Recursive-descent parser Ray Song Implementing a Simple Interpreter
  • 25. Tools Bison Can generate C, C++ and Java codes ANTLR Ray Song Implementing a Simple Interpreter
  • 26. Tools Bison Can generate C, C++ and Java codes ANTLR Ray Song Implementing a Simple Interpreter
  • 27. Tools Bison Can generate C, C++ and Java codes ANTLR Ray Song Implementing a Simple Interpreter
  • 28. Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
  • 29. Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
  • 30. Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
  • 31. Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
  • 32. Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
  • 33. Expression Precedence climbing method Shunting-yard algorithm Parsing expressions in in?x notation Output in Reverse Polish notation (RPN) Output in Abstract syntax tree (AST) Operator precedence parser Ray Song Implementing a Simple Interpreter
  • 34. Parser combinator Straightforward to construct Readability Parsec Ray Song Implementing a Simple Interpreter
  • 35. Parser combinator Straightforward to construct Readability Parsec Ray Song Implementing a Simple Interpreter
  • 36. Parser combinator Straightforward to construct Readability Parsec Ray Song Implementing a Simple Interpreter
  • 37. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 38. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 39. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 40. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 41. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 42. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 43. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 44. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 45. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 46. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 47. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 48. Impl Two top-level nonterminals: STMT and EXPR STMT: SIMPLE STMT ¡®n¡¯ | COMPOUND SIMPLE STMT: EXPR SIMPLE STMT: IDENT ¡®=¡¯ EXPR SIMPLE STMT: BREAK SIMPLE STMT: print EXPR COMPOUND: if EXPR ¡¯:¡¯ SUITE OPT ELSE COMPOUND: while EXPR ¡¯:¡¯ SUITE SUITE: many1(¡®n¡¯) INDENT many1(STMT) DEDENT SUITE: SIMPLE STMT ¡®n¡¯ OPT ELSE: ELSE ¡¯:¡¯ SUITE OPT ELSE: /* empty */ Ray Song Implementing a Simple Interpreter
  • 49. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 50. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 51. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 52. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 53. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 54. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 55. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 56. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 57. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 58. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 59. Impl - Cont. EXPR: EXPR ¡®==¡¯ TERM EXPR: EXPR ¡¯ !=¡¯ TERM EXPR: TERM TERM: TERM ¡®+¡¯ FACTOR TERM: FACTOR FACTOR: FACTOR ¡®*¡¯ ATOM FACTOR: ATOM ATOM: identi?er ATOM: literal integer ATOM: literal string ATOM: ¡®(¡¯ EXPR ¡¯)¡¯ Ray Song Implementing a Simple Interpreter
  • 60. Example if a > 2: print 5 print a Ray Song Implementing a Simple Interpreter
  • 61. Example - Cont. Figure : Parse Ray Song Implementing a Simple Interpreter
  • 62. Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
  • 63. Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
  • 64. Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
  • 65. Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
  • 66. Interpreting Abstract syntax tree (AST). De?ne semantics for each class of nodes object(atom): trivial binary operator BinOP(operator, lhs, rhs, RESULT) :- obj1 = eval(lhs), obj2 = eval(rhs), calc(op, obj1, obj2, RESULT). Object & BinOP inherit from Expr Ray Song Implementing a Simple Interpreter
  • 67. Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter
  • 68. Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter
  • 69. Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter
  • 70. Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter
  • 71. Subclasses of Stmt - Cont. Assign eval() need a parameter: Binding (which variable holds which object) ExprStmt Print Continue (throwing an exception) Ray Song Implementing a Simple Interpreter