Re: Parser Reversed

On 2018-03-11, Hans-Peter Diettrich <DrDiettrich1@netscape.net> 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
grammar.


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.

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