Re: Grammars with semantics

Hans Aberg wrote:


> Has somebody studied grammars G together with a semantics S in the sense
> below? -- Some common grammars are ambiguous, but even with a universal
> semantics, they may become unambiguous (meaning, different valid parses
> produce the same semantic value).
>
> Take the "calculator" grammar G = (T, N, P, E), terminals T = {i, `+',
> `*', `(', `)'}, nonterminals N = {E, T, F}, sentence symbol E, and the
> set of productions P containing:
> P_1: E -> T
> P_2: E -> E `+' T
> P_3: T -> F
> P_4: T -> T `*' F
> P_5: F -> i
> P_6: F -> `(' F `)'
>
> The expression i + i*i has several parses, for example the leftmost (as in
> LL, top-down, parsing) and rightmost (as in LR, bottom-up parsing):
>...
> So this grammar us ambiguous,


No, it's not. Top-down and bottom-up parsing produce the same parse-trees,
but they construct the nodes in different orders. An ambiguous grammar for
this language is one like:


                E -> i | '(' E ')' | | E '*' E | 'E' '+' 'E'


where there are several different ways of parsing say 'x + y * z * w'
corresponding to different ways of bracketing the operators.


[ I think you meant the F in the P_6 to be an E, but it's not important in
your example. ]


Very few grammars are "unambiguous" in the non-standard sense in which you
are using the term (essentially, only those in which the parse-trees
degenerate into lists).


> even though when imposing the condition that
> the rightmost or leftmost derivation should be used, the ambiguity
> disappears: So LL (if removing left recursion) and LR parsers would not
> complain.
>
>...
> Now, when I do that for the grammar G above, I get the same semantic value
> for the expression i + i * i for the leftmost and the rightmost parses,
> namely
> (f_2(f_1(f_3(f_5(x_1))), x_2, f_4(f_3(f_5(x_3)), x_4, f_5(x_5)))) in
> V^1
> if the value of the original string is (x_1, x_2, x_3, x_4, x_5) in V^5.
>
> Thus the funny thing happens that even though there are different parses
> of i + i*i, the "universal" semantic values agree.


The pattern of the applications of the f_i in your example is determined by
the structure of the parse-tree - as this is the same regardless of the
order in which you construct the nodes of the tree, the resulting
synthesized semantic value will be the same. What you're describing as the
"universal semantic value" _is_ the parse-tree.


In an implementation, if the evaluation of the f_i had side-effects, then
those side-effects would occur in a different sequence and that would
change the resulting semantic value.


>
> Now, has somebody written this phenomenon down, with conditions
> identifying semantically unambiguous grammars? References?
>


What you've described amounts to the observations that an unambiguous
grammar (in the usual sense of the term) assigns a unique parse-tree to
every sentence in its language and that evaluation of a side-effect free
function by recursion over the structure of a parse-tree is independent of
the order in which you calculate the values on the subtrees. This doesn't
sound deep enough for anyone to have written it up in those words - perhaps
you have a deeper question in mind that doesn't come over in your example.


Rob Arthan (rda@lemma-one.com)

Return to the comp.compilers page.
Search the comp.compilers archives again.