CS374: Programming Language Principles - Parsers and Interpreters

Activity Goals

The goals of this activity are:
  1. To remove left recursion and to left factor a grammar for LL(1) parsing, where possible
  2. To describe the components of an LL(k) and an LR(k) parser
  3. To implement a simple parser given a grammar, from code or using tools such as lex and yacc
  4. To generate a parse table for a given grammar

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity on the Class Activity Questions discussion board. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: An LL(1) Parser Implemented with Recursive Descent

Questions

  1. Try this example with some sample calculations.
  2. An LL(1) parser requires a grammar with no left recursion, and with unique nonterminals starting each production. Are these requirements met? If not, on what inputs will this parser fail? How can we fix it?

Model 2: An Alternative Grammar

Questions

  1. What is different about this grammar from the original one?

Model 3: Parsing with yacc

Questions

  1. How would you revise this to support the corrected LL(1) grammar?

Model 4: Generating an LR(0) Parse Table

Begin with a grammar definition:
Augment with a clean starting state:

State 0 is the S' -> .S initial state plus the closure, . indicates the S hasn't been read yet. Closure includes whatever can be produced by the production (plus any productions that can be executed from those - as indicated by a dot to the left of the nonterminal).

Now, transition from State 0 on each of the possible productions in the closure:
  • State 0 has 4 outputs upon reading S, X, x, and y. State 1: State 0 -> State 1 on reading S
    Move the dot to the right of the production that results from reading this transition, and perform the closure on productions that follow the dot (here, there are none). This state contains S' -> S.
  • State 2: State 0 -> State 2 on reading X
    S -> X.yx
  • State 3: State 0 -> State 3 on reading x
    X -> x.X; X -> .xX | .y
  • State 4: State 0 -> State 4 on reading y
    X -> y.
  • States 2 and 3 have additional outputs, so we proceed until the dot is all the way to the right. State 5: State 2 -> State 5 on reading y
    S -> Xy.x
  • State 6: State 3 -> State 6 on reading X
    X -> xX.
  • State 3 -> State 3 on reading x. Notice the productions in the closure are the same as in state 3.
    X -> x.X; X -> .xX | .y
  • Similarly, State 3 -> State 4 on reading y
  • Now, state 5 can continue - State 7: State 5 -> State 7 on reading x
    S -> Xyx.

Now the parse table: one state row per state above (0 through 7) ACTION is the set of terminals plus $ meaning the end of the string, and GOTO is the set of nonterminals besides the augmented first state S' -> S Fill in what state you go to if you read that terminal or nonterminal from that state. For example, state 0 goes to 1 on S, and it goes to 2 on X, per the rules at the top. Go to state 3 on x, and state 4 on y, and we call these shifts because the dot is still to the left of the end of the production, indicating a shift, as opposed to a reduce after the dot reaches the end of the production. The augmented state (state 1) accepts on end of string. The remaining states (4, 6, 7) have dots on the right. These are our reduce states. States 4 and 6 produce X, while state 7 produces S. State 4 is X -> y., State 6 is X -> xX., and State 7 is S -> Xyx.. We reduce these state rows to their corresponding production. X was initiated by state 2, due to its X. in the production, so we reduce on all inputs to r2 in state 4 and state 6. State 1 contains S. via S' -> S., so this is an r1 from state 7.
STATE ACTION x y $ GOTO S X
0 s3 s4 1 2
1 acc
2 s5
3 s3 s4 6
4 r2 r2 r2
5 s7
6 r2 r2 r2
7 r1 r1 r1

This can be programmed using an if statement (for example: if state == 0 and input == x, then state = 3, etc.). On reductions, you've read a whole statement. By shifting the individual tokens, you also know what inputs were provided to those productions. This is what tools like yacc do.

Questions

  1. Draw the state machine (the states and transitions) implemented by this LR(0) parse table.
  2. Augment the grammar and generate an LR(0) parse table for the grammar S -> XX; X -> xXy; X -> x; X -> y

Model 5: LR(0) Parse Tables

Wikipedia
Curr Lookahead LHS Goto
State Current Rules int id * + eof Sums Products Value
0 Goal → • Sums eof 8 9 1 4 7
1 Goal → Sums • eof
Sums → Sums • + Products		 2 done
2 Sums → Sums + • Products 8 9 3 7
3 Sums → Sums + Products •
Products → Products • * Value		 5 r1
 r1
4 Sums → Products •
Products → Products • * Value		 5 r2
 r2
5 Products → Products * • Value 8 9 6
6 Products → Products * Value • r3 r3 r3
7 Products → Value • r4 r4 r4
8 Value → int • r5 r5 r5
9 Value → id • r6 r6 r6

Questions

  1. Click on the image to see the steps involved with parsing A*2 + 1.
  2. Describe these steps in terms of the LR(0) parse table.
  3. What does the L, R, and 0 refer to in LR(0)?

Submission

Submit your answers to the questions using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section.