201506 CSE340 Lecture 11

CSE340 - Principles of
Programming Languages
Lecture 11:
Parser Implementation I
Javier Gonzalez-Sanchez
javiergs@asu.edu
BYENG M1-38
Office Hours: By appointment

Javier Gonzalez-Sanchez | CSE340 |Summer 2015 | 2
Parser
BNF
EBNF
A
AA
B
Parser
Grammar

Parser | Grammar 1
<EXPRESSION> à <X> {'|' <X>}
<X> à <Y> {'&' <Y>}
<Y> à ['!'] <R>
<R> à <E> {('>'|'<'|'=='|'!=') <E>}
<E> à <A> {(’+'|'-’) <A>}
<A> à {('*'|'/') }
 à ['-'] <C>
<C> à integer|
identifier|'(' <EXPRESSION> ')'

Parser | Grammar 2
<PROGRAM> à '{' <BODY> '}'
<BODY> à {<EXPRESSION>';'}
<EXPRESSION> à <X> {'|' <X>}
<X> à <Y> {'&' <Y>}
<Y> à ['!'] <R>
<R> à <E> {('>'|'<'|'=='|'!=') <E>}
<E> à <A> {(’+'|'-’) <A>}
<A> à {('*'|'/') }
 à ['-'] <C>
<C> à integer|
identifier|'(' <EXPRESSION> ')'

Parser | Input and Output
{
0;
1 + 2;
3 * (4 + hello);
}

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)
}

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 () {}
}

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

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

Parser
public static void RULE_EXPRESSION() {
RULE_X();
while (tokens.get(currentToken).getWord().equals(“|”)) {
currentToken++;
RULE_X();
}
}
EXPRESSION

Parser
public static void RULE_X() {
RULE_Y();
while (tokens.get(currentToken).getWord().equals(“&”)) {
currentToken++;
RULE_Y();
}
}
X

Parser
public static void RULE_Y() {
if (tokens.get(currentToken).getWord().equals(“!”)) {
currentToken++;
}
RULE_R();
}
Y

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

Parser
public static void RULE_E() {
RULE_A();
while (tokens.get(currentToken).getWord().equals(“-”)
| tokens.get(currentToken).getWord().equals(“+”)
) {
currentToken++;
RULE_A();
}
}
E

Parser
public static void RULE_A() {
RULE_B();
while (tokens.get(currentToken).getWord().equals(“/”)
| tokens.get(currentToken).getWord().equals(“*”)
) {
currentToken++;
RULE_B();
}
}
A

Parser
public static void RULE_B() {
if (tokens.get(currentToken).getWord().equals(“-”)) {
currentToken++;
}
RULE_C();
}
B

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

Homework
Programming Assignment 2
Level 1
Review and Understand the Source Code
posted in Blackboard. Specially, particularly the use of
DefaultMutableTreeNode)

Homework

Homework
Programming Assignment 2
Level 2
Modify the Source Code
to include the rules PROGRAM and BODY, EXPRESSION, X, Y, R
(from Grammar 2)

CSE340 - Principles of 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.

201506 CSE340 Lecture 11

Recommended

More Related Content

Viewers also liked (20)

Similar to 201506 CSE340 Lecture 11 (20)

More from Javier Gonzalez-Sanchez (20)

Recently uploaded (20)

201506 CSE340 Lecture 11