Build a parser generator that implements LL(1) PREDICT, FIRST and FOLLOW sets co

Question

Build a parser generator that implements LL(1) PREDICT, FIRST and FOLLOW sets construction in a purely functional subset of Scheme.

The key function you are to implement is the following:

(define parse-table

(lambda (grammar)

;;; your code here;

))

The input grammar must consist of a list of lists, one per non-terminal in the grammar. The first element of each sublist should be the non-terminal; the remaining elements should be the right-hand sides of the productions for which that non-terminal is the left-hand side. The sublist for the start symbol must come first. Every grammar symbol must be represented as a quoted string. As an example, here is our familiar LL(1) calculator grammar in the required format:

(define calc-gram

‘(("P" ("SL" "$$"))

("SL" ("S" "SL") ())

("S" ("id" ":=" "E") ("read" "id") ("write" "E"))

("E" ("T" "TT"))

("T" ("F" "FT"))

("TT" ("ao" "T" "TT") ())

("FT" ("mo" "F" "FT") ())

("ao" ("+") ("-"))

("mo" ("*") ("/"))

("F" ("id") ("num") ("(" "E" ")"))

))

Explanation / Answer

a parser generator that implements LL(1) PREDICT, FIRST and FOLLOW sets construction in a purely functional subset of Scheme.

The key function you are to implement is the following:

Build a parser generator that implements LL(1) PREDICT, FIRST and FOLLOW sets construction in a purely functional subset of Scheme.

The key function you are to implement is the following:

The input grammar must consist of a list of lists, one per non-terminal in the grammar. The first element of each sublist should be the non-terminal; the remaining elements should be the right-hand sides of the productions for which that non-terminal is the left-hand side. The sublist for the start symbol must come first. Every grammar symbol must be represented as a quoted string. As an example, here is our familiar LL(1) calculator grammar in the required format:

Build a parser generator that implements LL(1) PREDICT, FIRST and FOLLOW sets construction in a purely functional subset of Scheme.

The key function you are to implement is the following:

  (define parse-table      (lambda (grammar)      ;;; your code here;   ))  

The input grammar must consist of a list of lists, one per non-terminal in the grammar. The first element of each sublist should be the non-terminal; the remaining elements should be the right-hand sides of the productions for which that non-terminal is the left-hand side. The sublist for the start symbol must come first. Every grammar symbol must be represented as a quoted string. As an example, here is our familiar LL(1) calculator grammar in the required format:

  (define calc-gram      '(("P" ("SL" "$$"))        ("SL" ("S" "SL") ())        ("S" ("id" ":=" "E") ("read" "id") ("write" "E"))        ("E" ("T" "TT"))        ("T" ("F" "FT"))        ("TT" ("ao" "T" "TT") ())        ("FT" ("mo" "F" "FT") ())        ("ao" ("+") ("-"))        ("mo" ("*") ("/"))        ("F" ("id") ("num") ("(" "E" ")"))))  

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.