Re: Parser Reversed

Kaz Kylheku <>
Mon, 12 Mar 2018 21:00:36 +0000 (UTC)

          From comp.compilers

Related articles
Parser Reversed (Hans-Peter Diettrich) (2018-03-11)
Re: Parser Reversed (Matt P. Dziubinski) (2018-03-11)
Re: Parser Reversed (Kaz Kylheku) (2018-03-12)
Re: Parser Reversed (Hans-Peter Diettrich) (2018-03-13)
Re: Parser Reversed (Hans-Peter Diettrich) (2018-03-13)
| List of all articles for this month |

From: Kaz Kylheku <>
Newsgroups: comp.compilers
Date: Mon, 12 Mar 2018 21:00:36 +0000 (UTC)
Organization: NNTP Server
References: 18-03-038
Injection-Info:; posting-host=""; logging-data="32341"; mail-complaints-to=""
Keywords: parse, tools
Posted-Date: 12 Mar 2018 21:34:54 EDT

On 2018-03-11, Hans-Peter Diettrich <> wrote:
> A grammar can be used to *check* for valid sentences of a language, but
> it also can be used to *create* valid sentences.

Grammars are *defined* in terms of generation. That's why the rules are
called "production rules" not "recognition rules".

Using grammars to generate sentences randomly is algorithmically far
simpler than the cunning required to parse sentences according to a

It's a common homework exercise in the first week of compiler courses.
(Sometimes called compiler courses, though rarely do compilers
get written.)

If you can use a high level, dynamic language, you can probably
write the code on a napkin.

    let L := { S } # let L be a list containing the start symbol

    while (at least one non-terminal symbol remains in L) {
        choose a non-terminal symbol N from L
        choose from the grammar a production rule R which has N on its left
        replace S by the right side of the rule

    L now holds a random sentence

Note that if the grammar can generate infinite sentences, then this
algorithm has no guarantee of termination.

Some cunning could be built into such that, at a given configured
sentence length, it starts preferring the rules which lead to the
generation of terminal symbols.

If a given chosen N has two production rules like

    N -> N t # t is a terminal symbol
        -> t

then the second rule will be preferred (by some heuristic like choose
the rule with maximal terminal symbols and minimal non-terminals).

Speaking of termination, again, the generative POV dictates
the terminology: terminal symbols terminate the generation!

If the grammar isn't context free (two or more symbols appear on
the left hand side of a rule) then you have a more complicated
job. Basically you have to gather all the left hand patterns
from the grammar, and then look for occurences of these patterns
in the sentential form L. From these occurrences, pick one
and expand it. Something like that.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.