2
$\begingroup$

When designing a programming language, before even writing the compiler's code, what are existing tools allowing to write a grammar, which can then check it for ambiguities and test it with sample inputs ?

For example there is Antlr CLI: https://github.com/antlr/antlr4/blob/master/doc/tool-options.md, any other tools that can be used early in the design process ?

$\endgroup$
4
  • 3
    $\begingroup$ Welcome to PLDI! This is pretty opinion based currently, since what's best will depend heavily on what language you're using, what sort of language you're making, and what your priorities are (performance, helpful error messages, etc.). Rephrasing it to be more about the reasons you'd pick one over another will help you to get more objective answers. $\endgroup$ Commented May 23, 2023 at 22:07
  • $\begingroup$ Formal language theory concerns itself with ambiguities, but if you're writing a real programming language, you'll usually just cherrypick the "more intuitive" parse in that case. You deal with ambiguity by just deciding which one looks better. $\endgroup$ Commented May 23, 2023 at 22:15
  • $\begingroup$ Relevant meta quesiton about recommendations - languagedesign.meta.stackexchange.com/questions/261/… $\endgroup$ Commented May 25, 2023 at 8:09
  • $\begingroup$ mdaines.github.io/grammophone/# $\endgroup$
    – blueberry
    Commented Jun 19 at 1:33

2 Answers 2

5
$\begingroup$

This is more of a prototyping approach than a "checking" approach, but in the past, I have relied on LR parser generators which take a grammar-like input specification, check it for LR validity, and generate a parser for the specification.

Specifically, in Rust, I have made use of the LALRPOP tool for building parsers while I am in the "ideation" phase, and LALRPOP can produce helpful errors for a number of LR parsing ambiguities and issues.

Notably, I am pretty sure that LR parser generators tend to be somewhat strict, and may prevent you from expressing an otherwise valid or unambiguous production in your grammar, so it may not be suitable for all grammars or all levels of implementation.

$\endgroup$
-1
$\begingroup$

I saw tools for the automatic generation of random inputs, according with one specific grammar rule. All this in Smalltalk (SmaCC and PetiteParser had tools like that). But those was mechanisms (I guess) a bit different from what you are talking. They was viable because the two generators both had the lexer and the parser tied together.

Maybe more near to what you have in mind is another tool (still in Smalltalk). Ohm (which is the new incarnation of OMeta) and PetiteParser both gives the developer the freedom to test each grammar rule individually.

And that possibility is given by the particular design of those compilers, which are based on the concept of incremental composition of simple grammars. The whole parser is (maybe) a bit slower than other compiled and optimized grammars, but the phase of testing (which is hard, when the syntax is not super-simple, e.g. JavaScript is hard to test extensively) results more workable.

I'm personally working on a C++/JavaScript parser built with that logic and its not easy, but it is doable. I started with a parser for Lua... and testing it was a joke. Testing C++ or JavaScript... no, it's definitely not a joke.

New contributor
pber is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .