Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1998

Re: Parser Reversed

Show key headers only | View raw

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

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

DoDi

Back to comp.compilers | Previous | Next — Previous in thread | Find similar

Thread

Parser Reversed Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-03-11 08:32 +0100
  Re: Parser Reversed "Matt P. Dziubinski" <matdzb@gmail.com> - 2018-03-11 15:08 +0100
    Re: Parser Reversed Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-03-13 11:23 +0100
  Re: Parser Reversed Kaz Kylheku <157-073-9834@kylheku.com> - 2018-03-12 21:00 +0000
    Re: Parser Reversed Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-03-13 12:21 +0100

csiph-web