2
$\begingroup$

I often see syntax like

expression = term | expression, "+" , term;
term       = factor | term, "*" , factor;
factor     = constant | variable | "(" , expression , ")";
variable   = "x" | "y" | "z"; 

You see, all the rules produce an arithmetic value. Each can replace the other. Why not just declare

aexpr = var | num | (expr + expr) | expr * expr;

?

Certainly I need different production for expression of different type

statements = "if (" bexpr ") body | "while (" bexpr ")" body | a_variable "=" aexpr
bexpr = (bexpr "|" bexpr) | bexpr "&" bexpr | aexpr ">" aexpr

Here, I introduce a new production rule (a line per rule) only when I get a new type of expression and see no reason to split them.

I just started to generate random sentences and see that expressions are naturally grouped according their result type (e.g. arithmetic and boolean are different) and that is all. If you need an arithmetic expression, you draw (rewrite) it from arigthmetic pool, if boolean form the boolean pool. Why to split the pools into further groups?

$\endgroup$
  • $\begingroup$ In one word - ambiguity. In your suggested grammar, you can generate the same sentence in different ways. Sometimes, you want a grammar to be such that each sentence has a unique derivation tree $\endgroup$ – Roi Divon May 21 '14 at 11:38
  • $\begingroup$ @RoiDivon. Why not add a bit more explanation and turn this into an answer? $\endgroup$ – Rick Decker May 21 '14 at 11:40
2
$\begingroup$

In one word - ambiguity.

Sometime you don't want your grammar to be ambiugous.

For example, for parsing. Ambigous grammar can't have a $LR(K)$ grammar (you can think of ambiguity as non determinism). $LR(K)$ parser handle determinstic grammars.

Example for the ambiguity of your grammar:

Derivation tree 1

Derivation tree 2

The sentence a * b + c can be derived in two different ways.

$\endgroup$
  • $\begingroup$ Ok. I just do not notice the ambiguity perhaps because I have the expressions represented by trees in memory and wrapped em with "(" expr ")" parethises when write them out on the screen. $\endgroup$ – Val May 21 '14 at 12:12

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.