3 ms·
>> The novice programmer will ask, "what is a parser?" >> The intermediate programmer will say, "that's easy, I'll write a regular expression." >> The master
by YeGoblynQueenne 8y ago
>> The novice programmer will ask, "what is a parser?"
>> The intermediate programmer will say, "that's easy, I'll write a regular expression."
>> The master programmer will say, "stand back, I know lex and yacc."
The Prolog programmer will write a Definite Clause Grammar [1], which is both a grammar and a parser, two-in-one. So you only have to do the easy and fun bit of writing a parser, which is defining the grammar.
Leaves plenty of time to get online and brag about the awesome power of Prolog or get embroiled in flamewars with functional programming folks [2].
______________
[1] https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar
[2] Actually, DCGs are kiiind of like parser combinators. Ish. In the sense that they're executable grammars. But in Prolog you can run your programs backwards so your DCG is both a recogniser and a generator.
- fwip 8y agoThis is beside your point, but I've found PEG to be a nice step up in usability from lex&yacc, as again, you only have to write one grammar definition. Wiki: https://en.wikipedia.org/wiki/Parsing_expression_grammar https://en.wikipedia.org/wiki/Parsing_expression_grammar Example Implementation: https://pegjs.org/ https://pegjs.org/
- minxomat 8y agoYep, PEGs are seriously underutilized. Here's a nice introduction using LPeg: http://leafo.net/guides/parsing-expression-grammars.html http://leafo.net/guides/parsing-expression-grammars.html
- int_19h 8y agoFor Rust: https://github.com/kevinmehall/rust-peg https://github.com/kevinmehall/rust-peg
- thesz 8y agoRegarding your [2]. It is easy to combine parser and generator into one thing: http://hackage.haskell.org/package/reform http://hackage.haskell.org/package/reform (and then you can get to http://happstack.com/docs/crashcourse/Reform.html#reform http://happstack.com/docs/crashcourse/Reform.html#reform explaining how and how to).
- YeGoblynQueenne 8y agoIn Prolog it's not "easy"- it's implicit. You don't need to do anything special, you don't need to combine different programming constructs, you don't need a library and you don't even have to write your code in a special way to make your grammars work as parsers. The trick is that DCGs are Prolog programs, which is to say, they are logic theories that the Prolog interpreter proves true or false. Parsing a string then is a case of proving that the grammar is a theory that entails the string in its input (with some abuse of terminology!). And because a Prolog predicate (including each rule in a definite clause grammar) is a relation rather than a function, and so has no fixed inputs and outputs, you can leave the "input" unbound, to generate all strings entailed by the grammar. Yes? You write a grammar. You get you recognisers for nothing and your generators for free.
- russed 8y agoPlease share any examples you know of on how to do this!
- YeGoblynQueenne 8y agoThe wikipedia article has a few examples. For instance: sentence --> noun_phrase, verb_phrase. noun_phrase --> det, noun. verb_phrase --> verb, noun_phrase. det --> [the]. det --> [a]. noun --> [cat]. noun --> [bat]. verb --> [eats]. And here are some example queries: % Running as a recogniser ?- sentence([the,cat,eats,a,cat], []). true. % With a string not in the grammar ?- sentence([the,cat,eats,'YeGoblynQuenne'], []). false. % Running as a generator ?- sentence(P, []). P = [the, cat, eats, the, cat] ; P = [the, cat, eats, the, bat] ; P = [the, cat, eats, a, cat] ; P = [the, cat, eats, a, bat] ; P = [the, bat, eats, the, cat] ; P = [the, bat, eats, the, bat] ; P = [the, bat, eats, a, cat] ; % ... % More results generated on backtracking To prevent any confusion - the "A --> B" syntax is syntactic sugar. Such statements are expanded to ordinary Prolog terms by the Prolog equivalent of a macro (an expansion hook). You can inspect the ordinary Prolog definitions saved in the program database: ?- listing(sentence). sentence(A, B) :- noun_phrase(A, C), verb_phrase(C, B). Indeed, it's perfectly possible to write these by hand - as you can see above the ordinary Prolog definition is not that complicated, the macro expanding the DCG notation adds two variables to each nonterminal and relieves you of the need to add this boilerplate yourself.