**This is an old revision of the document!**

Table of Contents


  • Understand how some grammars require back-tracking to parse because it isn't possible to predict perfectly which production should be used.
  • Understand how to do parsing using table-driven parsing and recursive descent parsing for LL(1) grammars


  • Recursive descent parsing
  • Backtracking and the use of a stack in parsing
  • LL(1) grammars
  • FIRST and FOLLOW sets
  • Constructing a table for table-driven parsing with and without FIRST and FOLLOW sets
  • Using the call stack via recursive function calls in recursive-descent parsing


  1. (4 points) Show the top-down recursive parse with no look-ahead for the input int / int. When choosing which rule to expand, go in order of the rules. The int terminal is an integer literal).
    <E> ::= <T> - <E> | <T>
    <T> ::= ( <E> ) | int | int / <T>
  2. (2 points) Compute the FIRST sets for the following. Compute FOLLOW sets as well for extra credit.
    <A> ::= <A><A>'+' | <A><A>'*' | a
  3. (6 points) For each of the following grammars, devise predictive parsers and show the parsing tables. You may left-factor and/or eliminate left-recursion from your grammars first if needed:
    1. S –> 0 S 1 | 0 1
    2. S –> + S S | * S S | a
    3. S –> S ( S ) S | lambda
  4. (8 points) Build the LL(1) parse table for the following grammar with start symbol X. You may left-factor or remove left-recursion if needed.
    <X> ::= (<P>)
    <P> ::= <Z><P> | <Z>
    <Z> ::= 0 | 1
  5. (4 points) The following is a grammar for regular expressions over symbols a and b only, using + in place of | for union, to avoid conflict with the use of vertical bar as a meta-symbol in grammars:
    <rexpr> ::= <rexpr> '+' <rterm> | <rterm>
    <rterm> ::= <rterm> <rfactor> | <rfactor>
    <rfactor> ::= <rfactor> '*' | <rprimary>
    <rprimary> ::= 'a' | 'b'
    • Is the grammar ready for LL(1) parsing? If yes, then justify your answer. If no, then modify the grammar so it is LL(1).
cs-236/homework-4.1443479009.txt.gz · Last modified: 2015/09/28 16:23 by egm
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0