# Some terminologies in Wirth's book and the satisfying of deterministic algorithm

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 :

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

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 ?

• Please replace the image with text, to make the text searchable. Commented Sep 22, 2017 at 21:16
• 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. Commented Sep 23, 2017 at 0:46

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.