Re: Parser Reversed

Hans-Peter Diettrich <>
Tue, 13 Mar 2018 12:21:58 +0100

          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: Hans-Peter Diettrich <>
Newsgroups: comp.compilers
Date: Tue, 13 Mar 2018 12:21:58 +0100
Organization: Compilers Central
References: 18-03-038 18-03-044
Injection-Info:; posting-host=""; logging-data="59977"; mail-complaints-to=""
Keywords: code
Posted-Date: 13 Mar 2018 15:34:36 EDT

Am 12.03.2018 um 22:00 schrieb Kaz Kylheku:
> 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".

Isn't that depending on the grammar notation?

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

Right, at least as long as semantical correctness is not of interest.

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

I'm near 50 years past that stage ;-)

> 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

Ah, double randomization is a nice trick :-)

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

Right. I thought of giving weights to the alternatives of a NT, and
using multiple sets of weights for initial, continued and final stage of
the generation.

> 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.

Fine, with eps (empty) counting as a terminal symbol.

> 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).

In my simple grammar case this will be sufficient. Other grammars may
deserve some initial analysis.

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

Point taken :-)

> 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.

This is where replacing the (sequentially) first matching pattern may
not cover all cases of interest.

Thanks for the many hints :-)


Post a followup to this message

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