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
Exprfollowed directly by the literal
b, it may be expanded to
ba, and may be expanded again producing
baaand this process repeats infinitely to produce
baaa, and so on.
I have tried to visualize this grammar as follows:
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
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:
baa ^ found termination, expected "a"
Appreciate any guidance you can provide me in thinking about this problem.