0
$\begingroup$

I don't "see" why the following syntax is equivalent to the second

syntax1:

E -> E + T
E -> T

syntax2:

E -> T E'
E' -> + T E'
E' ->

(it is to avoid left recursion and I am not understanding why the solution works)

How do I mathematically prove that both syntax definitions are equivalent

$\endgroup$
3
$\begingroup$

An intuitive approach towards the difference is understanding that the productions of syntax #1 add new material to the left of existing symbols whereas those of syntax #2 do so on the right-hand side.

  • syntax #1:

    derived string of terminals: `  T    + T   + T  ...  + T   + T `
    derivation step:             `[ n ] [n-1] [n-2]     [ 2 ] [ 1 ]`
    
  • syntax #2 (step #n is the application of rule 3 and produces no terminal) :

    derived string of terminals: `  T    + T   + T  ...  + T   + T `
    derivation step:             `[ 1 ] [ 2 ] [ 3 ]     [n-2] [n-1]`
    

for a rigorous proof note that under both syntaxes, each derivation leads to an initial T followed by sequence of + T. for the grammars at hand this can be proven by induction over the number of rule applications.

$\endgroup$
0

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.