Parser: Difference between revisions

Parser (view source)

Revision as of 18:29, 4 January 2024

738 bytes added , 4 January

m

ramble about greedy PEG parsers

Laqme

Bureaucrats, Interface administrators, Suppressors, Administrators

685

edits

@@ Line 1: / Line 1: @@
 Toaq's grammar can be parsed by humans and computers alike. A piece of software that turns Toaq text into a syntax tree is called a '''parser'''.
+== Parsers ==
+[https://github.com/toaq/kuna Kuna] is a WIP parser for Toaq Delta.
+Outdated parsers can be found for Toaq Gamma [[zugai|here]], and for Toaq Beta [https://toaq-dev.github.io/toaq.org/parser/ here] and [[Mıu|here]]. Hoemaı wrote an [http://selpahi.de/toaq.txt early version of Toaq grammar in Prolog].
 == Grammar formats ==
-It's popular to write parsers in [https://en.wikipedia.org/wiki/Parsing_expression_grammar PEG] format. In practice, PEG parser generators disagree on the specifics of the <code>.peg</code> format, meaning a PEG grammar tends to be tied to a specific implementation (say, PEGjs).
+In the past, it has been common to write parsers in [https://en.wikipedia.org/wiki/Parsing_expression_grammar PEG] format. In practice, PEG parser generators disagree on the specifics of the <code>.peg</code> format, meaning a PEG grammar tends to be tied to a specific implementation (say, PEGjs).
 [[Hoemaı]] thinks PEG is not a good fit for Toaq. In fact, PEG can only describe [https://en.wikipedia.org/wiki/Context-free_language context-free languages], which Toaq is not. See their blog post [https://toaqlanguage.wordpress.com/2022/09/26/logical-language-misconceptions/ ''Logical Language Misconceptions''] for more information.
-== Parsers ==
+One problem with PEG grammars is that they resolve ambiguities "greedily": if there would be multiple parses for a sentence, a PEG parser returns only the one it finds first. In this way, a language described by a PEG grammar is automatically [[monoparsing]], but in an obscure and unsatisfying way. Alternative parses are ruled out not through linguistic rules, but by implementation details of the PEG software, such as which branches it tries first or the order in which rules are specified in the .peg file.
-There is currently no parser for Toaq text, mostly because we set the bar very high for what counts as a parser. [https://github.com/toaq/kuna Kuna] is a WIP parser for Toaq Delta.
-Outdated parsers can be found for Toaq Gamma [[zugai|here]], and for Toaq Beta [https://toaq-dev.github.io/toaq.org/parser/ here] and [[Mıu|here]]. Hoemaı wrote an [http://selpahi.de/toaq.txt early version of Toaq grammar in Prolog].
+[[Kuna]] uses an [https://en.wikipedia.org/wiki/Earley_parser Earley parser] to describe a context-free approximation of surface-level Toaq. The multiple parses are then fixed up or rejected using TypeScript code. Once the implementation is completely correct, this will always result in either one parse or no parse.