5 ms·

Regarding your [2]. It is easy to combine parser and generator into one thing: http://hackage.haskell.org/package/reform http://hackage.haskell.org/package/ref

• YeGoblynQueenne 8y ago
  In 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 ago
    Please share any examples you know of on how to do this!
    • YeGoblynQueenne 8y ago
      The 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.
  • thesz 8y ago
    Oh, you need to do more than "nothing special" in Prolog to get anything that is mildly useful. The very notion of constraint programming was born in Prolog community to handle... well, to handle constraint programming better than regular Prolog handles it. Let me bring you another example. In case of parser combinators over lists you can have a greedy alternative: newtype P a = P (String -> [(String, a)] -- a parser is a function from input to remaining input and result. P a <|> P b = P $ \s -> case a s of [] -> b s xs -> xs The regular alternative is this: P a <|> P b = P $ \s -> a s ++ b s You can use combinators like that: many, some :: P a -> P [a] -- possible empty parse - returns empty list for that many item = some item <|> pure [] -- parse head item and tail list of items and combine into a list some item = (:) <$> item <*> many item This greedy thing above helps greatly when you are dealing with mostly regular grammars (which are aplenty in wild) - it does not hold input for too long, it is faster for no parse situation, etc. You put a change in a single combinator function and get wastly improved result. In case of Prolog handling grammars you would have to put cuts all over your grammar definition, risking either loss of specification equivalence or performance. I have more practical questions. For example, how would you design online parsers - ones that consume item by item and produce intermediate results on the go? How would you design a tree of parsers for editor to speed up reparsing after change? These kinky Applicative and Alternative combinators let you not to worry about details when specifying the grammar. You specify it with class (pun intended - abstract getting an item into a class and you are done) and lay above the implementation which can be wholesome, streaming, with partial parses, deterministic, etc.
    • YeGoblynQueenne 8y ago
      >> Oh, you need to do more than "nothing special" in Prolog to get anything that is mildly useful. This is really not my experience. I've been coding in Prolog for 10 years and done a bunch of useful stuff, if I say so myself (my latest baby: https://github.com/stassa/metasplain https://github.com/stassa/metasplain). Constraint (logic) programming is cool and useful, but it's not necessary. It's just a particular logic programming paradigm. Actually, although I do find it very nice and pure, in a declarative sense, I don't think I could code all my stuff in CLP. I can't say I understand your parser combination notation. The syntactic sugar of DCGs means that if you can read BNF, you can read a DCG. Simple syntax that doesn't get in your way when you're trying to do complicated things is a hallmark of Prolog in general. Cuts are also not necessary- DCGs are one kind of Prolog program where I almost never use cuts. One reason for that is that you usually want your grammars to be nondeterministic, so that you can use them as generators. DCGs basically just process lists, so it's not usually that hard to ensure a grammar doesn't overgenerate. You really don't have much use of cuts with DCGs, unless you use them to write arbitrary Prolog programs, rather than parsers (which you can do, since DCGs are syntacitc sugar for ordinary Prolog- but I generally don't). The online grammar outputting intermediary results you're describing, I think you're talking about something like this (not tested): s --> a, b. a --> [a], {writeln('Found an a')}. b --> [b], {writeln('Found a b')}. The curly braces, {}, embed arbitrary Prolog code in the body of a rule (which btw makes DCGs Turing-complete, I guess) that is executed as soon as it's found in the body of the grammar. You can go a long way with it. The "parser tree" you describe would probably need some coding around the grammars, i.e. you'd have to write special code to combine a few parsers. Or maybe not, I'm not sure because I haven't tried to do what you say. What do you use something like that for?