armchair_progamer

armchair_progamer, 1 month ago

Java the language, in human form.

armchair_progamer, 1 month ago (edited 28 days ago)

I find writing the parser by hand (recursive descent) to be easiest. Sometimes I use a lexer generator, or if there isn’t a good one (idk for Scheme), write the lexer by hand as well. Define a few helper functions and macros to remove most of the boilerplate (you really benefit from Scheme here), and you almost end up writing the rules out directly.

Yes, you need to manually implement choice and figure out what/when to lookahead. Yes, the final parser won’t be as readable as a BNF specification. But I find writing a hand-rolled parser generator for most grammars, even with the manual choice and lookahead, is surprisingly easy and fast.

The problem with parser generators is that, when they work they work well, but when they don’t work (fail to generate, the generated parser tries to parse the wrong node, the generated parser is very inefficient) it can be really hard to figure out why. A hand-rolled parser is much easier to debug, so when your grammar inevitably has problems, it ends up taking less time in total to go from spec to working hand-rolled vs. spec to working parser-generator-generated.

The hand-rolled rules may look something like (with user-defined macros and functions define-parse, parse, peek, next, and some simple rules like con-id and name-id as individual tokens):

<span style="color:#323232;">; pattern			::= [ con-id ] factor "begin" expr-list "end"
</span><span style="color:#323232;">(define-parse pattern
</span><span style="color:#323232;">  (mk-pattern
</span><span style="color:#323232;">    (if (con-id? (peek)) (next))
</span><span style="color:#323232;">    (parse factor)
</span><span style="color:#323232;">    (do (parse “begin”) (parse expr-list) (parse “end”))))
</span><span style="color:#323232;">
</span><span style="color:#323232;">; factor 			::= name-id 
</span><span style="color:#323232;">; 			 | symbol-literal
</span><span style="color:#323232;">; 			 | long-name-id 
</span><span style="color:#323232;">; 			 | numeric-literal 
</span><span style="color:#323232;">;	 		 | text-literal 
</span><span style="color:#323232;">; 			 | list-literal 
</span><span style="color:#323232;">; 			 | function-lambda 
</span><span style="color:#323232;">; 			 | tacit-arg
</span><span style="color:#323232;">; 			 | '(' expr ')' 
</span><span style="color:#323232;">(define-parse factor
</span><span style="color:#323232;">  (case (peek)
</span><span style="color:#323232;">    [name-id? (if (= “.” (peek2)) (mk-long-name-id …) (next))]
</span><span style="color:#323232;">    [literal? (next)]
</span><span style="color:#323232;">    …))
</span>

Since you’re using Scheme, you can almost certainly optimize the above to reduce even more boilerplate.

Regarding LLMs: if you start to write the parser with the EBNF comments above each rule like above, you can paste the EBNF in and Copilot will generate rules for you. Alternatively, you can feed a couple EBNF/code examples to ChatGPT and ask it to generate more.

In both cases the AI will probably make mistakes on tricky cases, but that’s practically inevitable. An LLM implemented in an error-proof code synthesis engine would be a breakthrough; and while there are techniques like fine-tuning, I suspect they wouldn’t improve the accuracy much, and certainly would amount to more effort in total (in fact most LLM “applications” are just a custom prompt on plain ChatGPT or another baseline model).

armchair_progamer, 1 month ago

!https://www.unix.date/#two