I am doing homework and I have the following problem:

Consider the grammar:

statement → assign 
statement → sub_call 
assignment → id = expression 
sub_call → id ( arguments ) 
expression → head tail 
tail → operation expression
tail → ε 
head → id 
head → sub_call 
head → ( expression ) 
operation → + | - | * | / 
arguments → expression arg_tail 
arg_tail → , arguments 
arg_tail → ε

Construct a parse tree for the input string:

 foo(a , b)

Add the production rules necessary to extend this grammar to include the definition of a subroutine. For example:

subroutine foo (x, y) { 
z = x + y 
bar(z) } 

What I've Considered

I am somewhat familiar with trees that use expressions,literal, and variables but this is so much more and I can't think of where to even begin. Not to mention create a tree for a subroutine. Could someone please help me with this? How do I even start?

  • 2
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Apr 4 '16 at 7:35
  • $\begingroup$ Hint: use any parsing algorithm suitable for this grammar. $\endgroup$
    – Raphael
    Apr 4 '16 at 7:35
  • $\begingroup$ If you are familiar with Prolog, you could have used Definite Clause Grammar construct in it: it would almost literally translate your pseudo-code into actual code you could run on different inputs to test and see what works. $\endgroup$
    – wvxvw
    Apr 4 '16 at 7:36

It's not actually that much more, it just feels daunting because the syntax is different.

Creating a parse tree

In general, a parse tree is built out of the production rules in your grammar.

A simple string like x + y will have a derivation1 like:

expression => head tail
           => head operation expression
           => head operation head tail
           => head operation head ε
           => head operation id ε
           => id operation id ε

You can use this derivation to build a parse tree, the root of which will be he non-terminal expression, the leaves of which will be the terminals id, operation, id, and ε, and the interior nodes of which will be assorted non-terminals; I'll leave it as an exercise to figure out the specifics.

To build a parse tree for foo(a , b), you would do exactly the same thing: find a derivation, and then convert it into a parse tree.

Adding production rules

This is a slightly harder problem, in my opinion, but still not too bad. I would suggest starting by sketching out what you think a derivation should look like, and then add the production rules you need.

1 This is a right-derivation, but you could also do a left-derivation by expanding the non-terminals from left-to-right rather than from right-to-left. I'm not sure how you've been taught, so do what you've been told


Below is Prolog DCG for your requirement (using SWI Prolog):

:- use_module(library(dcg/basics)).

id_first --> [X], { code_type(X, csymf) }.
id_rest  --> [X], id_rest, { code_type(X, csym) } | [].
id       --> id_first, id_rest.
space    --> [X], space, { code_type(X, space) } | [].
end      --> [10].
op       --> `+` | `-` | `*` | `/`.

expression  --> subcall | arith_exp | id.
args        --> space, expression, space
              | expression, space, `,`, space, args
              | space.
ids         --> space, id, space
              | space, id, space, `,`, space, ids
              | space.
line        --> space, assignment, space, end
              | space, expression, space, end.
expressions --> line | line, expressions | space.
assignment  --> id, space, `=`, space, expression.
subcall     --> id, `(`, args, `)`.
arith_exp   --> space, id, space
              | space, subcall, space
              | space, id, space, op , space, arith_exp.
signature   -->  id, space, `(`, ids, `)`.
subroutine  --> `subroutine`, space, signature, space, `{`,
                  space, end, expressions, `}`.

I think, that it is easier to start with something that gives you feedback as you try to improve on it. You can test this grammar by typing something like:

?- phrase(subroutine, `subroutine x (y, q) { 
x = y
y = func(x + z)
 } some junk`, X), string_codes(Y, X).
|    X = [32, 115, 111, 109, 101, 32, 106, 117, 110|...],
Y = " some junk" .

Into Prolog interactive shell after you've loaded the predicates. phrase/3 predicate has this meaning: phrase(A, B, C) - A is the grammar to use to parse B string, while the part of B which failed to parse will be stored in C.

As to your specific question, you can think about it like so: you need a rule that only matches something that starts with the exact string subroutine followed by Id variable, followed by exact string (, followed by the list of arguments Arguments, followed by exact string ), followed by exact string {, followed by Block (of code), ending in exact string }.

Note that Block uses the same principle as Arguments, so it's either nothing, a single expression or a single expression followed by a Block of code.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.