1
$\begingroup$

I am going through Wirth's Textbook on Compiler design . After proceeding though some pages , I realized I have taken for granted my understanding of some of the terminologies that have been used . For example ,the following terms :

enter image description here

the examples mentioned in the lines in the screenshot refer to the following set of equations :

enter image description here

Later on while describing the possibility of the conditions of deterministic algorithms being satisfied it says for an expresion of the following form :

"term_0 | term_1"

the terms must not feature any common starting symbols .And then it says this results in the exclusion of left recusrsion . If we consider the left recursive production :

A = A "a" | "b"

then the requirement is violated "b" is also a start symbol of "A" .

How is "b" a start symbol of "A" ? Basically from the definitions given I understood start symbol means the symbol for which an equation is deifined first ?

Why does common start symbol disturb the conditions of deterministic algorithm ?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Please replace the image with text, to make the text searchable. $\endgroup$
    – Yuval Filmus
    Commented Sep 22, 2017 at 21:16
  • $\begingroup$ Welcome to Computer Science! We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$
    – Raphael
    Commented Sep 23, 2017 at 0:46

1 Answer 1

Reset to default
3
$\begingroup$

The definition of start symbol that you quote has nothing to do with the definition of start symbol in the context of deterministic grammars. Here is a correct definition:

A terminal $a$ is a start symbol of a sequential form $\alpha$ if $\alpha \Rightarrow^* aw$ for some $w \in \Sigma^*$.

In words, $a$ is a start symbol of $\alpha$ if $\alpha$ generates some word starting in $a$.

In your example, $Aa$ generates the word $ba$, and so it shares a start symbol with $b$.

Why is sharing a start symbol bad? Suppose you are trying to parse $A$, and are encountering $b$. Which production do you choose? $Aa$ or $b$? It is impossible to tell without looking ahead. The deterministic algorithm considered by Wirth has no lookahead, and so this situation is problematic for it.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Thanks a lot for your reply . Any material that you can suggest for learning about this topic ? $\endgroup$
    – Eddie Dorphy
    Commented Sep 23, 2017 at 6:42
  • $\begingroup$ Wirth's book is really old fashioned. Pick up a more recent one. $\endgroup$
    – Yuval Filmus
    Commented Sep 23, 2017 at 6:43
  • $\begingroup$ Would I be right if i say that the pre-requisites haven't been arranged in a proper sequence , like , it comes up with few things which requires prior explanation which are missing ? Any suggestions for other books ? A one that is legally available for free in pdf format will be nice . $\endgroup$
    – Eddie Dorphy
    Commented Sep 23, 2017 at 6:50
  • $\begingroup$ Where can I find the definition of start symbok that you have quoted in your anser ? $\endgroup$
    – Eddie Dorphy
    Commented Sep 23, 2017 at 6:52
  • $\begingroup$ The definition is pretty standard. I bet you can find it in the "dragon" book. Unfortunately textbooks tend not to be freely available, but you can find them on libraries. $\endgroup$
    – Yuval Filmus
    Commented Sep 23, 2017 at 6:54

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.