IN2009 Language Processors

FIND A SOLUTION AT Academic Writers Bay

IN2009 Language Processors: 5
Coursework
1
2
Contents
• The LPL parser code:
–Comparison with Turtle Graphics
• Terminology:
–LL grammars/recursive-descent
parsers
• Parser development: unit testing
• Hints, Q&A
Coursework
Compare LPL with TurtleGraphics
3
Turtle Graphics
Coursework
JavaCC file
Turtle.jj
LPL.jj
Productions
TProgram(), TCommand(),
TBlock()
nt_Program,
nt_Exp(),
nt_Statement(), etc
AST
TurtleProgram,
TurtleCommand, …
Program, Exp,
Statement, …
Top-level
program
turtle.Parse
turtle.Print
lpl.Parse
lpl.print
• Reminder: the LPL grammar has features
which make it unsuitable for direct
implementation by a recursive-descent parser
– Left-recursion
– Choice-conflicts
• You need to resolve these issues
4
But LPL is harder to implement…
LL Grammars and LL Parsers
• LL Parser is just another name for RecursiveDescent Parser
• An LL grammar is a grammar that can be
parsed by an LL parser
• An LL(k) grammar is an LL grammar that can
be parsed with no more than k-tokens of lookahead
– So to parse an LL(1) grammar an LL
parser only needs to look at the first token
in the current token stream, etc
5
Limitations of JavaCC
• JavaCC can only generate parsers for
LL grammars
–By default it assumes the grammar is
LL(1)
–If the grammar is not LL(1) we must:
• Either: use LOOKAHEAD directives to
tell JavaCC where it needs to look
further along the token stream
• Or: factor the grammar 6
Statement ® id = Exp ;
® if ( Exp ) Statement else Statement
® id ( ExpList )
7
Reminder: choice-conflict
public void Statement() :<ID> <LB> ExpList <RB> <SEMICOLON>8
Reminder: the problem
void Statement()
if (tok==ID)
eat(ID); eat(EQ); Exp(); eat(SEMICOLON);
else if (tok==IF)
eat(IF); eat(LB); Exp(); eat(RB);
Statement(); eat(<ELSE>); Statement();
else if(tok==ID)
eat(ID); eat(LB); ExpList(); eat(RB);
else
error();
Unreachable case
Choiceconflict
9
Reminder: a solution
public void Statement() :<IF> <LB> Exp() <RB> Statement() <ELSE> Statement()10
How the solution works
void Statement()
if (toks(0)==ID && toks(1)==EQ)
eat(ID); eat(EQ); Exp(); eat(SEMICOLON);
else if (toks(0)==IF)
eat(IF); eat(LB); Exp(); eat(RB);
Statement(); eat(<ELSE>); Statement();
else if(toks(0)==ID)
eat(ID); eat(LB); ExpList(); eat(RB);
else
error();
Reachable
11
Rule-order
• Irrelevant in a CFG but not in JavaCC
• This would not work:
public void Statement() :<IF> <LB> Exp() <RB> Statement() <ELSE> Statement()12
Non-solution
void Statement()
if(toks(0)==ID)
eat(ID); eat(LB); ExpList(); eat(RB);
else if (toks(0)==ID && toks(1)==EQ)
eat(ID); eat(EQ); Exp(); eat(SEMICOLON);
else if (toks(0)==IF)
eat(IF); eat(LB); Exp(); eat(RB);
Statement(); eat(<ELSE>); Statement();
else else
error();• Where is the conflict?
• Good news!
– JavaCC will find it for you and tell you
where it is
• Hint:
– Read the details of warnings and error
messages
– They usually tell you quite precisely what
needs to be fixed
13
Some choice-conflicts can be harder to
spot…
S ® a X | T b
T ® b a S | a S
X ® c | d
Unit Testing
• Test nt_Exp(), nt_Statement(),
nt_FunDef(), etc as you go
– don’t wait until the whole parser is complete
• Edit Parse.java to call parser.nt_Exp() (or
parser.nt_Statement() or
parser.nt_FunDef(), etc) instead of
parser.nt_Program()
• Use the LPL grammar to derive instances of Exp
(or Statement, or FunDef, etc) to use as test
inputs
14
Unit Testing Example
• Suppose you have a partial implementation of
the PrimaryExp grammar:
public void nt_PrimaryExp() :<TRUE>15
Unit Testing Example: continued
1. Edit Parse.java and change the call
parser.nt_Program();
to
parser.nt_PrimaryExp();
2. Compile everything
3. Use the PrimaryExp grammar to generate some test strings, eg:
PrimaryExp ⇨ 73
PrimaryExp ⇨ 0
PrimaryExp ⇨ true
PrimaryExp ⇨ isnull PrimaryExp ⇨ isnull 73
PrimaryExp ⇨ isnull PrimaryExp
⇨ isnull isnull PrimaryExp
⇨ isnull isnull true
4. Put each one in a separate file and run Parse on each of them.
16
Testing your Semantic Actions
• Hint: add toString() methods to the AST
classes before you add semantic actions
– This way you can use lpl.Print to see what
AST your parser is building
• Also: follow the testing advice in the coursework
document!
17

READ ALSO...   Supportive Submission
Order from Academic Writers Bay
Best Custom Essay Writing Services

QUALITY: 100% ORIGINAL PAPERNO PLAGIARISM – CUSTOM PAPER