I am considering this left recursive language grammar production rule:

Expr = Expr, "a" ;

As a production rule, I believe that this can be used to produce an infinite sequence of aaa by describing the rule like this:

Given a non-terminal Expr, expand it to Expr followed directly by the literal a.

Example: if Expr is initially b, it may be expanded to ba. Expr is now ba, and may be expanded again producing baa and this process repeats infinitely to produce ba, baa, baaa, and so on.

I have tried to visualize this grammar as follows:

grammar production visualized

I believe the grammar cannot terminate in its production, as it requires infinite recursion (in theory.)

Given that this is a valid production rule, I would believe that it is possible this grammar could also then be used as the definition to write a parser. I would describe that parser as:

It accepts any sequence of non-terminals (the Expr) followed by an infinite sequence of a.

However, what is not clear to me is if a parser for this language would require an infinite sequence of a or if a finite sequence of a would be admissible: would baa actually be a valid input, or would a theoretical machine parser for this effectively produce an error saying:

   ^ found termination, expected "a"

Appreciate any guidance you can provide me in thinking about this problem.

  • $\begingroup$ I assume that you are talking about a grammar that consists only of this rule (otherwise the question is unclear. I also don't understand where "b" comes from if this is the only rule in your grammar). This grammar corresponds to an empty language: there is no string $s$ (must be a finite sequence of terminals, by definition) which can be derived from this grammar. Any reasonable parser generator should be able to detect it, and therefore the resulting parser will simply reject any string. $\endgroup$
    – user114966
    Apr 3 at 4:41
  • $\begingroup$ "I assume that you are talking about a grammar that consists only of this rule" Yes. $\endgroup$ Apr 3 at 6:11
  • $\begingroup$ @Dmitry Thank you for the explanation and definition of a grammar link. Based on that and your comment, my understanding is that you are effectively saying that my example grammar does not have a starting symbol 𝑠 (in the definition) and is therefor invalid according to the definition. I am not sure I understand why a reasonable parser would "simply reject any string" though instead of "produce an error stating the grammar is invalid" then? Is there precedence for how parsers should handle grammars with a missing 𝑠? $\endgroup$ Apr 3 at 7:27
  • $\begingroup$ Also, if you want to submit what you said as an answer I will mark it as such. $\endgroup$ Apr 3 at 7:36
  • $\begingroup$ In practice, Iit’s up to parser what to do with incorrect strings. If the string is correct, a parser will build a syntax tree (maybe implicitly). If it’s not correct, it may try to recover a close correct string, print some kind of error, throw exception, etc. In case of empty language, I would print an error during parser generation. $\endgroup$
    – user114966
    Apr 3 at 16:56

Your grammar captures the empty language. To see this, you need to use the definition of a language described by a context-free grammar.

A context-free grammar is a tuple $(T,N,S,P)$, where $T$ is the set of terminals (a non-empty finite set), $N$ is the set of nonterminals (a non-empty finite set disjoint from $T$), $S \in N$ is the starting symbol, and $P$ is a collection of productions $A \to \alpha$, where $A \in N$ and $\beta \in (N \cup T)^*$.

In your case, $T = \{a\}$, $N = \{\mathrm{Expr}\}$, $S = \mathrm{Expr}$ (you are not stating this explicitly, but this is the only choice), and $P$ consists of the single rule $\mathrm{Expr} \to \mathrm{Expr} \, a$.

We say that $\beta$ produces $\gamma$ in one step, in symbols $\beta \Rightarrow \gamma$, if there exists a production $A \to \alpha \in P$ and two strings $\lambda,\mu \in (N \cup T)^*$ such that $\beta = \lambda A \mu$ and $\gamma = \lambda \alpha \mu$.

We say that $\beta$ produces $\gamma$, in symbols $\beta \Rightarrow^* \gamma$, if either $\gamma = \beta$, or $\beta \Rightarrow \delta \Rightarrow^* \gamma$ for some $\delta \in (N \cup T)^*$. This is the reflexive-transitive closure of $\Rightarrow$.

Finally, the language produced by the grammar is $\{ w \in T^* : S \Rightarrow^* w \}$.

In your case, a simple induction shows that $\mathrm{Expr} \Rightarrow^* \alpha$ iff $\alpha = \mathrm{Expr} \, a^n$ for some $n \in \mathbb{N}$. Since $\mathrm{Expr} \, a^n \notin T^*$, we conclude that the language produced by your grammar is the empty language.


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.