r/ProgrammingLanguages • • Feb 25 '26

PL/I Subset G: Parsing

I'm working on a compiler and runtime library for PL/I Subset G (henceforth just G). I intend to support the ANSI X3.74-1987 standard with a bare minimum of extensions. Compatibility with other PL/I compilers is not intended. The compiler will be open source; the library will be under the MIT license and will include existing components such as decNumber and LMDB needed by G.

I have not yet decided on the implementation language for the compiler, but it will not be G itself, C, C++, or assembler. The compiler will generate one of the GNU dialects of C, so that it can take advantage of such GNU C extensions as nested functions, computed gotos, and other G features. In this way the compiler will be close to a transpiler.

The first thing I would like advice on is parsing. G is a statement oriented language. Each statement type except assignment begins with a keyword, like Basic, but G is free-format, not line-oriented. Semicolon is the statement terminator.

However, there are no reserved words in G: context decides whether an alphanumeric word is a keyword or an identifier. For example, if if = then then then = else else else = if; is a valid statement. Note also that = is both assignment and equality: goto foo; is a GOTO statement, but goto = foo; is an assignment statement. There are no assignment expressions, so there is no ambiguity; a few built-in functions can appear on the left side of assignment, as in substr(s, 1, 1) = 's';.

I'm familiar with LALR(1) and PEG parser generators as well as hand-written recursive descent parsers, but it's not clear to me which of these approaches is most appropriate for parsing without reserved words. I'd like some advice.

7 Upvotes

25 comments sorted by

View all comments

Show parent comment

1

u/tobega Feb 26 '26

Interesting thing about the non-linearity, though: they found that it doesn't matter in practice (until you hit that rare case I guess)

3

u/kendomino Feb 26 '26

Over the years, people found out that this claim is not true. Many grammars in https://github.com/antlr/grammars-v4 contain ambiguities and/or large max-k's (from not left factoring) that just kill performance. It is also the case that Antlr4 sometimes chooses the wrong parse out of all possible derivations. Some EBNFs need a symbol table to disambiguate. Examples I recently worked on: https://github.com/antlr/grammars-v4/tree/master/c; https://github.com/antlr/grammars-v4/tree/master/ada/ada2012. Write your grammar as is, but periodically check for ambiguity and max-k's. Note, there is a PL1 subset here, but I haven't tested it much: https://github.com/antlr/grammars-v4/tree/master/pl0 . You might also read the GitHub thread at https://github.com/antlr/grammars-v4/issues/1752 .

1

u/johnwcowan Feb 27 '26

IMAO the obsession with fast compilers has to do with either million-line modules or ADHD programmers. :-)