## Description

Theoretical background

A derivation is a rule list that describes how to derive a phrase from a nonterminal symbol. For example,

suppose we have the following grammar with start symbol Expr:

Expr → Term Binop Expr

Expr → Term

Term → Num

Term → Lvalue

Term → Incrop Lvalue

Term → Lvalue Incrop

Term → “(” Expr “)”

Lvalue → $ Expr

Incrop → “++”

Incrop → “−−”

Binop → “+”

Binop → “−”

Num → “0”

Num → “1”

Num → “2”

Num → “3”

Num → “4”

Num → “5”

Num → “6”

Num → “7”

Num → “8”

Num → “9”

Then here is a derivation for the phrase “3” “+” “4” from the nonterminal Expr. After each rule is applied, the

resulting list of terminals and nonterminals is given.

rule after rule is applied

(at start) Expr

Expr → Term Binop Expr Term Binop Expr

Term → Num Num Binop Expr

Num → “3” “3” Binop Expr

Binop → “+” “3” “+” Expr

Expr → Term “3” “+” Term

Term → Num “3” “+” Num

Num → “4” “3” “+” “4”

In a leftmost derivation, the leftmost nonterminal is always the one that is expanded next. The above example is

a leftmost derivation.

Motivation

You’d like to test grammars that are being proposed as test cases for CS 132 projects. One way is to test it on

actual CS 132 projects, but those projects aren’t done yet and anyway you’d like a second opinion in case the

student projects are incorrect. So you decide to write a simple parser generator. Given a grammar in the style of

Homework 1, your program will generate a function that is a parser. When this parser is given a program to

parse, it produces a derivation for that program, or an error indication if the program contains a syntax error and

cannot be parsed.

The key notion of this assignment is that of a matcher. A matcher is a function that inspects a given string of

terminals to find a match for a prefix that corresponds to a nonterminal symbol of a grammar, and then checks

whether the match is acceptable by testing whether a given acceptor succeeds on the corresponding derivation

and suffix. For example, a matcher for awkish_grammar below might inspect the string [“3″;”+”;”4″;”-“] and

find two possible prefixes that match, namely [“3″;”+”;”4″] and [“3”]. The matcher will first apply the

acceptor to a derivation for the first prefix [“3″;”+”;”4″], along with the corresponding suffix [“-“]. If this is

accepted, the matcher will return whatever the acceptor returns. Otherwise, the matcher will apply the acceptor

to a derivation for the second prefix [“3”], along with the corresponding suffix [“+”;”4″;”-“], and will return

whatever the acceptor returns. If a matcher finds no matching prefixes, it returns the special value None.

As you can see by mentally executing the example, matchers sometimes need to try multiple alternatives and to

backtrack to a later alternative if an earlier one is a blind alley.

An acceptor is a function that accepts a rule list and a suffix by returning some value wrapped inside the Some

constructor. The acceptor rejects the rule list and suffix by returning None. For example, the acceptor (fun d ->

function | “+”::t -> Some (d,”+”::t) | _ -> None) accepts any rule list but accepts only suffixes

beginning with “+”. Such an acceptor would cause the example matcher to fail on the prefix [“3″;”+”;”4″]

(since the corresponding suffix begins with “-“, not “+”) but it would succeed on the prefix [“3”].

By convention, an acceptor that is successful returns Some (d,s), where d is a rule list that typically contains the

acceptor’s input rule list as a sublist (because the acceptor may do further parsing, and therefore has applied more

rules than before), and s is a tail of the input suffix (again, because the acceptor may have parsed more of the

input, and has therefore consumed some of the suffix). This allows the matcher’s caller to retrieve the derivation

for the matched prefix, along with an indication where the matched prefix ends (since it ends just before the

suffix starts). Although this behavior is crucial for the internal acceptors used by your code, it is not required for

top-level acceptors supplied by test programs: a top-level acceptor needs only to return a Some x value to

succeed.

Whenever there are several rules to try for a nonterminal, you should always try them left-to-right. For example,

awkish_grammar below contains this:

| Expr ->

[[N Term; N Binop; N Expr];

[N Term]]

and therefore, your matcher should attempt to use the rule “Expr → Term Binop Expr” before attempting to use

the simpler rule “Expr → Term”.

Definitions

12/13/2018 Homework 2. Naive parsing of context free grammars

https://web.cs.ucla.edu/classes/fall18/cs131/hw/hw2.html 3/7

symbol, right hand side, rule

same as in Homework 1.

alternative list

A list of right hand sides. It corresponds to all of a grammar’s rules for a given nonterminal symbol. By

convention, an empty alternative list [] is treated as if it were a singleton list [[]] containing the empty

symbol string.

production function

A function whose argument is a nonterminal value. It returns a grammar’s alternative list for that

nonterminal.

grammar

A pair, consisting of a start symbol and a production function. The start symbol is a nonterminal value.

derivation

a list of rules used to derive a phrase from a nonterminal. For example, the OCaml representation of the

example derivation shown above is as follows:

[Expr, [N Term; N Binop; N Expr];

Term, [N Num];

Num, [T “3”];

Binop, [T “+”];

Expr, [N Term];

Term, [N Num];

Num, [T “4”]]

fragment

a list of terminal symbols, e.g., [“3”; “+”; “4”; “xyzzy”].

acceptor

a curried function with two arguments: a derivation d and a fragment frag. If the fragment is not

acceptable, it returns None; otherwise it returns Some x for some value x.

matcher

a curried function with two arguments: an acceptor accept and a fragment frag. A matcher matches a

prefix p of frag such that accept (when passed a derivation and the corresponding suffix) accepts the

corresponding suffix (i.e., the suffix of frag that remains after p is removed). If there is such a match, the

matcher returns whatever accept returns; otherwise it returns None.

Assignment

1. To warm up, notice that the format of grammars is different in this assignment, versus Homework 1. Write

a function convert_grammar gram1 that returns a Homework 2-style grammar, which is converted from

the Homework 1-style grammar gram1. Test your implementation of convert_grammar on the test

grammars given in Homework 1. For example, the top-level definition let awksub_grammar_2 =

convert_grammar awksub_grammar should bind awksub_grammar_2 to a Homework 2-style grammar that

is equivalent to the Homework 1-style grammar awksub_grammar.

2. Write a function parse_prefix gram that returns a matcher for the grammar gram. When applied to an

acceptor accept and a fragment frag, the matcher must return the first acceptable match of a prefix of frag,

by trying the grammar rules in order; this is not necessarily the shortest nor the longest acceptable match.

A match is considered to be acceptable if accept succeeds when given a derivation and the suffix fragment

that immediately follows the matching prefix. When this happens, the matcher returns whatever the

acceptor returned. If no acceptable match is found, the matcher returns None.

3. Write two good, nontrivial test cases for your parse_prefix function. These test cases should all be in the

style of the test cases given below, but should cover different problem areas. Your test cases should be

named test_1 and test_2 (note the underscores; this distinguishes your test cases from the standard ones

given below). Your test cases should test at least one grammar of your own. You may reuse your test cases

for Homework 1 as part of test_1, but test_2 should be new.

4. Assess your work by writing an after-action report that summarizes why you solved the problem the way

you did, other approaches that you considered and rejected (and why you rejected them), and any

12/13/2018 Homework 2. Naive parsing of context free grammars

https://web.cs.ucla.edu/classes/fall18/cs131/hw/hw2.html 4/7

weaknesses in your solution in the context of its intended application. If possible, illustrate weaknesses by

test cases that fail with your implementation. This report should be a simple ASCII plain text file that

consumes a page or so (at most 100 lines and 80 columns per line, and at least 50 lines, please). See

Resources for oral presentations and written reports for advice on how to write assessments; admittedly

much of the advice there is overkill for the simple kind of report we’re looking for here.

Unlike Homework 1, we are expecting some weaknesses here, so your assessment should talk about them. For

example, we don’t expect that your implementation will work with all possible grammars, but we would like to

know which sort of grammars it will have trouble with.

As with Homework 1, your code may use the Pervasives and List modules, but it should use no other

modules. Your code should be free of side effects. Simplicity is more important than efficiency, but your code

should avoid using unnecessary time and space when it is easy to do so.

Submit

We will test your program on the SEASnet Linux servers as before, so make sure that /usr/local/cs/bin is at

the start of your path, using the same technique as in Homework 1.

Submit three files:

hw2.ml should define parse_prefix along with any auxiliary types and functions needed to define

parse_prefix.

hw2test.ml should contain your test cases.

hw2.txt should hold your assessment.

Please do not put your name, student ID, or other personally identifying information in your files.

Sample test cases

let accept_all derivation string = Some (derivation, string)

let accept_empty_suffix derivation = function

| [] -> Some (derivation, [])

| _ -> None

(* An example grammar for a small subset of Awk.

This grammar is not the same as Homework 1; it is

instead the same as the grammar under

“Theoretical background” above. *)

type awksub_nonterminals =

| Expr | Term | Lvalue | Incrop | Binop | Num

let awkish_grammar =

(Expr,

function

| Expr ->

[[N Term; N Binop; N Expr];

[N Term]]

| Term ->

[[N Num];

[N Lvalue];

[N Incrop; N Lvalue];

[N Lvalue; N Incrop];

[T”(“; N Expr; T”)”]]

| Lvalue ->

[[T”$”; N Expr]]

| Incrop ->

12/13/2018 Homework 2. Naive parsing of context free grammars

https://web.cs.ucla.edu/classes/fall18/cs131/hw/hw2.html 5/7

[[T”++”];

[T”–“]]

| Binop ->

[[T”+”];

[T”-“]]

| Num ->

[[T”0″]; [T”1″]; [T”2″]; [T”3″]; [T”4″];

[T”5″]; [T”6″]; [T”7″]; [T”8″]; [T”9”]])

let test0 =

((parse_prefix awkish_grammar accept_all [“ouch”]) = None)

let test1 =

((parse_prefix awkish_grammar accept_all [“9”])

= Some ([(Expr, [N Term]); (Term, [N Num]); (Num, [T “9”])], []))

let test2 =

((parse_prefix awkish_grammar accept_all [“9”; “+”; “$”; “1”; “+”])

= Some

([(Expr, [N Term; N Binop; N Expr]); (Term, [N Num]); (Num, [T “9”]);

(Binop, [T “+”]); (Expr, [N Term]); (Term, [N Lvalue]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term]); (Term, [N Num]);

(Num, [T “1”])],

[“+”]))

let test3 =

((parse_prefix awkish_grammar accept_empty_suffix [“9”; “+”; “$”; “1”; “+”])

= None)

(* This one might take a bit longer…. *)

let test4 =

((parse_prefix awkish_grammar accept_all

[“(“; “$”; “8”; “)”; “-“; “$”; “++”; “$”; “–“; “$”; “9”; “+”;

“(“; “$”; “++”; “$”; “2”; “+”; “(“; “8”; “)”; “-“; “9”; “)”;

“-“; “(“; “$”; “$”; “$”; “$”; “$”; “++”; “$”; “$”; “5”; “++”;

“++”; “–“; “)”; “-“; “++”; “$”; “$”; “(“; “$”; “8”; “++”; “)”;

“++”; “+”; “0”])

= Some

([(Expr, [N Term; N Binop; N Expr]); (Term, [T “(“; N Expr; T “)”]);

(Expr, [N Term]); (Term, [N Lvalue]); (Lvalue, [T “$”; N Expr]);

(Expr, [N Term]); (Term, [N Num]); (Num, [T “8”]); (Binop, [T “-“]);

(Expr, [N Term; N Binop; N Expr]); (Term, [N Lvalue]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term; N Binop; N Expr]);

(Term, [N Incrop; N Lvalue]); (Incrop, [T “++”]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term; N Binop; N Expr]);

(Term, [N Incrop; N Lvalue]); (Incrop, [T “–“]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term; N Binop; N Expr]);

(Term, [N Num]); (Num, [T “9”]); (Binop, [T “+”]); (Expr, [N Term]);

(Term, [T “(“; N Expr; T “)”]); (Expr, [N Term; N Binop; N Expr]);

(Term, [N Lvalue]); (Lvalue, [T “$”; N Expr]);

(Expr, [N Term; N Binop; N Expr]); (Term, [N Incrop; N Lvalue]);

(Incrop, [T “++”]); (Lvalue, [T “$”; N Expr]); (Expr, [N Term]);

(Term, [N Num]); (Num, [T “2”]); (Binop, [T “+”]); (Expr, [N Term]);

(Term, [T “(“; N Expr; T “)”]); (Expr, [N Term]); (Term, [N Num]);

(Num, [T “8”]); (Binop, [T “-“]); (Expr, [N Term]); (Term, [N Num]);

(Num, [T “9”]); (Binop, [T “-“]); (Expr, [N Term]);

(Term, [T “(“; N Expr; T “)”]); (Expr, [N Term]); (Term, [N Lvalue]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term]); (Term, [N Lvalue]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term]); (Term, [N Lvalue]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term]); (Term, [N Lvalue; N Incrop]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term]); (Term, [N Lvalue; N Incrop]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term]); (Term, [N Incrop; N Lvalue]);

(Incrop, [T “++”]); (Lvalue, [T “$”; N Expr]); (Expr, [N Term]);

(Term, [N Lvalue; N Incrop]); (Lvalue, [T “$”; N Expr]); (Expr, [N Term]);

(Term, [N Num]); (Num, [T “5”]); (Incrop, [T “++”]); (Incrop, [T “++”]);

12/13/2018 Homework 2. Naive parsing of context free grammars

https://web.cs.ucla.edu/classes/fall18/cs131/hw/hw2.html 6/7

(Incrop, [T “–“]); (Binop, [T “-“]); (Expr, [N Term]);

(Term, [N Incrop; N Lvalue]); (Incrop, [T “++”]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term]); (Term, [N Lvalue; N Incrop]);

(Lvalue, [T “$”; N Expr]); (Expr, [N Term]);

(Term, [T “(“; N Expr; T “)”]); (Expr, [N Term]);

(Term, [N Lvalue; N Incrop]); (Lvalue, [T “$”; N Expr]); (Expr, [N Term]);

(Term, [N Num]); (Num, [T “8”]); (Incrop, [T “++”]); (Incrop, [T “++”]);

(Binop, [T “+”]); (Expr, [N Term]); (Term, [N Num]); (Num, [T “0”])],

[]))

let rec contains_lvalue = function

| [] -> false

| (Lvalue,_)::_ -> true

| _::rules -> contains_lvalue rules

let accept_only_non_lvalues rules frag =

if contains_lvalue rules

then None

else Some (rules, frag)

let test5 =

((parse_prefix awkish_grammar accept_only_non_lvalues

[“3”; “-“; “4”; “+”; “$”; “5”; “-“; “6”])

= Some

([(Expr, [N Term; N Binop; N Expr]); (Term, [N Num]); (Num, [T “3”]);

(Binop, [T “-“]); (Expr, [N Term]); (Term, [N Num]); (Num, [T “4”])],

[“+”; “$”; “5”; “-“; “6”]))

Sample use of test cases

If you put the sample test cases into a file hw2sample.ml, you should be able to use it as follows to test your

hw2.ml solution on the SEASnet implementation of OCaml. Similarly, the command #use “hw2test.ml”;;

should run your own test cases on your solution.

$ ocaml

OCaml version 4.04.0

# #use “hw2.ml”;;

…

val parse_prefix :

‘a * (‘a -> (‘a, ‘b) symbol list list) ->

((‘a * (‘a, ‘b) symbol list) list -> ‘b list -> (‘c list * ‘d) option) ->

‘b list -> (‘c list * ‘d) option =

…

# #use “hw2sample.ml”;;

val accept_all : ‘a -> ‘b -> (‘a * ‘b) option =

val accept_empty_suffix : ‘a -> ‘b list -> (‘a * ‘c list) option =

type awksub_nonterminals = …

val awkish_grammar :

awksub_nonterminals *

(awksub_nonterminals -> (awksub_nonterminals, string) symbol list list) =

(Expr,

val test0 : bool = true

val test1 : bool = true

val test2 : bool = true

val test3 : bool = true

val test4 : bool = true

val contains_lvalue : (awksub_nonterminals * ‘a) list -> bool =

val accept_only_non_lvalues :

(awksub_nonterminals * ‘a) list ->

‘b -> ((awksub_nonterminals * ‘a) list * ‘b) option =

val test5 : bool = true

#

12/13/2018 Homework 2. Naive parsing of context free grammars

https://web.cs.ucla.edu/classes/fall18/cs131/hw/hw2.html 7/7

Hint

You can use a previous Homework 2 as a hint. It is a tough homework and is not the same problem but there are

some common ideas. Look for the sample solution at the end.

© 2003, 2004, 2006–2012, 2014–2017 Paul Eggert. See copying rules.

$Id: hw2.html,v 1.65 2017/10/23 00:49:12 eggert Exp $