Path: csiph.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Kaz Kylheku <157-073-9834@kylheku.com> Newsgroups: comp.compilers Subject: Re: Parser Reversed Date: Mon, 12 Mar 2018 21:00:36 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 52 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <18-03-044@comp.compilers> References: <18-03-038@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="32341"; mail-complaints-to="abuse@iecc.com" Keywords: parse, tools Posted-Date: 12 Mar 2018 21:34:54 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1992 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 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.