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?

Improve this question
$\endgroup$
2
  • $\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
    Commented May 21, 2014 at 11:38
  • $\begingroup$ @RoiDivon. Why not add a bit more explanation and turn this into an answer? $\endgroup$
    – Rick Decker
    Commented May 21, 2014 at 11:40

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented May 21, 2014 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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