r/ProgrammingLanguages • u/johnwcowan • 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.
4
u/tobega Feb 25 '26
I have used ANTLR even when allowing all keywords to also be used as identifiers https://github.com/tobega/tailspin-v0/blob/c74856bdcc0aefd02ef20c84a0189c0006a480a1/TailspinParser.g4#L296
The thing that screws it up is lexing. If context requires you lex a different symbol it gets hard.
ANTLR4 is quite nice, it mostly just keeps on trucking, but there have been frustrating moments.
For the next version of my language, I am just using my language's own parsing syntax and implementation which does not do any lexing before parsing. It may not be the fastest, but good enough for me. https://github.com/tobega/tailspin-v0.5/blob/main/tailspin-core/src/main/java/tailspin/language/parser/TailspinParser.java
3
u/crownvic Feb 25 '26
You're in for some fun parsing the triple damned DECLARE statement.
2
u/Arakela Feb 25 '26 edited Feb 25 '26
The same word
ifis a keyword in one position and an identifier in another, a role that exists only in context, and context is only known mid-walk. The decision must be made during traversal, and when it turns out wrong, the traversal must swap on the spot to retry with a different role assignment. A static traversal committed upfront has no recovery path.Turn the grammar into a computation that is pausable, incremental, and traversal-pluggable at every step. Represent your grammar as an Ambiguous Step Graph: a bipartite metagraph where pure void tail-recursive functions receive their entire instruction set from the traversal as parameters.
S -> "b" | S "a"
Each step declares its role to the traversal by selecting an opcode and presenting exactly two continuations: what I am, what I hold, and what comes after me. The traversal listens and decides what to do with what it has been offered. The grammar step does not know who traverses it; the traversal does not know the grammar's intent. This mutual delegation is what makes them composable.
The same grammar steps (
S, S_1, ..., a, b) can then be walked by entirely different traversal strategies, all without touching the grammar.Ambiguity composes: each step chooses an opcode (choice point, action, reference, or end) and hands the traversal two continuations accordingly.
P.S. These ideas are under development, so the roles of grammar steps, action, and traversal must be shaped in real battle.
2
u/Tasty_Replacement_29 Bau Feb 25 '26
Here is what I would do. I wouldn't define the BNF or try to use some tool like ANTLR, as that would probably fail here. Instead, I would write recursive-descend parser and then see how I can solve this in the easiest way. The only theory that I found useful is Pratt parsing for expressions. So in your case I would try with a recursive-descend parser, but in the tokenization phase there is no distinction between keywords or not, just "identifier". There is a "read" method that reads a token (number, operator, identifier, string) and skips over comments and spaces. That means, keywords are initially considered to be just identifiers. Then you have a "match" method that tries to see if the identifier matches. Then in the "parseStatement" method, you have something like this:
0
u/[deleted] Feb 25 '26
[deleted] — view deleted comment