![Javier Gonzalez-Sanchez | CSE340 |Summer 2015 | 3 Parser | Grammar 1 <EXPRESSION> à <X> {'|' <X>} <X> à <Y> {'&' <Y>} <Y> à ['!'] <R> <R> à <E> {('>'|'<'|'=='|'!=') <E>} <E> à <A> {(’+'|'-’) <A>} <A> à <B> {('*'|'/') <B>} <B> à ['-'] <C> <C> à integer| identifier|'(' <EXPRESSION> ')'](https://image.slidesharecdn.com/cse34011parser1-150609000611-lva1-app6892/75/201506-CSE340-Lecture-11-3-2048.jpg)
![Javier Gonzalez-Sanchez | CSE340 |Summer 2015 | 4 Parser | Grammar 2 <PROGRAM> à '{' <BODY> '}' <BODY> à {<EXPRESSION>';'} <EXPRESSION> à <X> {'|' <X>} <X> à <Y> {'&' <Y>} <Y> à ['!'] <R> <R> à <E> {('>'|'<'|'=='|'!=') <E>} <E> à <A> {(’+'|'-’) <A>} <A> à <B> {('*'|'/') <B>} <B> à ['-'] <C> <C> à integer| identifier|'(' <EXPRESSION> ')'](https://image.slidesharecdn.com/cse34011parser1-150609000611-lva1-app6892/75/201506-CSE340-Lecture-11-4-2048.jpg)
Uploaded byJavier Gonzalez-Sanchez
201506 CSE340 Lecture 11
This document contains slides from a lecture on parser implementation. It introduces BNF and EBNF notation for context-free grammars and shows example grammars for expressions. It then outlines the steps to implement a parser according to a given grammar using a recursive descent approach. Code snippets are provided for various parser rules corresponding to the grammar rules. The slides conclude by assigning homework to modify the provided source code to implement additional grammar rules for a programming language.
201506 CSE340 Lecture 11
- 1. CSE340 - Principlesof Programming Languages Lecture 11: Parser Implementation I Javier Gonzalez-Sanchez javiergs@asu.edu BYENG M1-38 Office Hours: By appointment
- 2. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 2 Parser BNF EBNF A AA B Parser Grammar
- 3. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 3 Parser | Grammar 1 <EXPRESSION> à <X> {'|' <X>} <X> à <Y> {'&' <Y>} <Y> à ['!'] <R> <R> à <E> {('>'|'<'|'=='|'!=') <E>} <E> à <A> {(’+'|'-’) <A>} <A> à <B> {('*'|'/') <B>} <B> à ['-'] <C> <C> à integer| identifier|'(' <EXPRESSION> ')'
- 4. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 4 Parser | Grammar 2 <PROGRAM> à '{' <BODY> '}' <BODY> à {<EXPRESSION>';'} <EXPRESSION> à <X> {'|' <X>} <X> à <Y> {'&' <Y>} <Y> à ['!'] <R> <R> à <E> {('>'|'<'|'=='|'!=') <E>} <E> à <A> {(’+'|'-’) <A>} <A> à <B> {('*'|'/') <B>} <B> à ['-'] <C> <C> à integer| identifier|'(' <EXPRESSION> ')'
- 5. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 5 Parser | Input and Output { 0; 1 + 2; 3 * (4 + hello); }
- 6. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 6 Parser | Step by Step For each rule in the grammar { § Step 1. left-hand side (new method) § Step 2. right-hand side (loops, ifs, call methods) § Step 3. identify errors (terminals) § Step 4. synchronize errors (first and follow sets) }
- 7. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 7 Parser public class Parser { private static Vector<Token> tokens; private static int currentToken; public static void RULE_PROGRAM () {} public static void RULE_BODY () {} public static void RULE_EXPRESSION () {} public static void RULE_X () {} public static void RULE_Y () {} public static void RULE_R () {} public static void RULE_E () {} public static void RULE_A () {} public static void RULE_B () {} public static void RULE_C () {} }
- 8. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 8 Parser public static void RULE_PROGRAM() { if (tokens.get(currentToken).getWord().equals(“{”)) { currentToken++; else error(1); RULE_BODY(); if (tokens.get(currentToken).getWord().equals(“}”)) currentToken++; else error(2); } PROGRAM
- 9. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 9 Parser public static void RULE_BODY() { while (!tokens.get(currentToken).getWord().equals(“}”)) { RULE_EXPRESSION(); if (tokens.get(currentToken).getWord().equals(“;”)) currentToken++; else error(3); } } BODY
- 10. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 10 Parser public static void RULE_EXPRESSION() { RULE_X(); while (tokens.get(currentToken).getWord().equals(“|”)) { currentToken++; RULE_X(); } } EXPRESSION
- 11. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 11 Parser public static void RULE_X() { RULE_Y(); while (tokens.get(currentToken).getWord().equals(“&”)) { currentToken++; RULE_Y(); } } X
- 12. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 12 Parser public static void RULE_Y() { if (tokens.get(currentToken).getWord().equals(“!”)) { currentToken++; } RULE_R(); } Y
- 13. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 13 Parser public static void RULE_R() { RULE_E(); while ( tokens.get(currentToken).getWord().equals(“<”) |tokens.get(currentToken).getWord().equals(“>”) |tokens.get(currentToken).getWord().equals(“==”) |tokens.get(currentToken).getWord().equals(“!=”) ) { currentToken++; RULE_E(); } } R
- 14. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 14 Parser public static void RULE_E() { RULE_A(); while (tokens.get(currentToken).getWord().equals(“-”) | tokens.get(currentToken).getWord().equals(“+”) ) { currentToken++; RULE_A(); } } E
- 15. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 15 Parser public static void RULE_A() { RULE_B(); while (tokens.get(currentToken).getWord().equals(“/”) | tokens.get(currentToken).getWord().equals(“*”) ) { currentToken++; RULE_B(); } } A
- 16. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 16 Parser public static void RULE_B() { if (tokens.get(currentToken).getWord().equals(“-”)) { currentToken++; } RULE_C(); } B
- 17. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 17 Parser public static void RULE_C() { if (tokens.get(currentToken).getToken().equals(“integer”)) { currentToken++; } else if (tokens.get(currentToken).getToken().equals(“identifier”)) { currentToken++; } else if (tokens.get(currentToken).getWord().equals(“(”)) { currentToken++; RULE_EXPRESSION(); if (tokens.get(currentToken).getWord().equals(“)”)) { currentToken++; } else error(4); } } else { error (5); } } C
- 18. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 18 Homework Programming Assignment 2 Level 1 Review and Understand the Source Code posted in Blackboard. Specially, particularly the use of DefaultMutableTreeNode)
- 19. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 19 Homework
- 20. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 20 Homework
- 21. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 21 Homework
- 22. Javier Gonzalez-Sanchez |CSE340 |Summer 2015 | 22 Homework Programming Assignment 2 Level 2 Modify the Source Code to include the rules PROGRAM and BODY, EXPRESSION, X, Y, R (from Grammar 2)
- 23. CSE340 - Principlesof Programming Languages Javier Gonzalez-Sanchez javiergs@asu.edu Summer 2015 Disclaimer. These slides can only be used as study material for the class CSE340 at ASU. They cannot be distributed or used for another purpose.