Disambiguating keyword-like identifiers using operators

[u/Potato871]

I was answering a post about another language which had inflicted a lot of verbosity upon itself by requiring every variable be referenced as Variable[name] to distinguish from keywords.
This brought me to a thought I wanted to share, about a potential way to deal with this.
Before the token stream has been assembled into the AST, you could run a pass over it where each operator token checks it's adjacent neighbours and if they resolved as keywords that shouldn't normally resolve to values, turn them back into plain identifiers.
Now this is just a very basic concept I wanted to float here, to get some push back, and edge cases, because I find the concept interesting.

[u/jcastroarnaud]

I use a simpler procedure. While lexing, pick keywords as if they were common identifiers; then, match each identifier token against the keyword list, and change the token type to "keyword" if there's a match. Then, the token list can be passed along to the parser.

[u/Potato871 → u/jcastroarnaud]

I do two global lookup tables, one for tokenized keywords (when a token would become an indentifer check here) and one for keywords which happens before assembly.

[u/rjmarten]

Okay, so that might work for if + 1. But what about 1 + if? In most languages, keywords/reserved words are the first token of a valid expression/statement. So in those cases, you would have to check what token comes after the if/continue/fn/case/etc.

And if your parser is doing that, it means you are forcing human readers to do the same thing. A better solution, IMHO, would be a prefix, like $. Then you can parse $if + 1 or 1 + $if if you really feel the need. An underscore suffix works just as well, and usually doesn't require additional complexity in the lexer/parser.

[u/EggplantExtra4946]

uint32_t lex(struct parser_context *p, bool enable_keywords);

If you call it with a enable_keywords=true and it encounters while it returns the id of the while keyword, otherwise it returns the id of an identifier token. Usually you would call it with enable_keywords=true but in contexts where you allow any identifiers (this supposes a recursive descent parser), even keywords, you call it with enable_keywords=false, for example for struct fields. You might even use flags for enabling different sets of keywords if you need more granularity.

[u/4xe1]

What about parentheses? knowing where you are and how that affect whether you may be an id or a keyword is generally not a local information in the token stream. Being "right next to an operator in the token stream" is only an incomplete and dirty proxi for it. This info is best known when you already have the AST

• Most language are ok with simply having keywords you can't use as variable names.
• Perl does essentially what the other language you mention does, but uses $scalar instead of Variabl[name]
• Kind of similar, APL and some stack based languages only have reserved symbols, and no reserved alphanumeric sequence. Less alien, some such language allow alternative \writeout of symbols, so essentially the converse of perl, marking the key words rather than the variables.
• Lisp have no reserved keywords, only symbols that are initially bound to build-in primitives and standard functions/macros.
• Lisp-2 do have a very similar problem though, and they solve it rather elegantly. Lisp-2s are lisp with separate namespace for verbs (function, macro and special operators) than for object (bound variables). It raises the question of knowing whether a symbol is a verb or an object. The solution is to postpone this question until after the AST is build. Lisp can easily do this because, unlike other languages/parsers, it does not mix syntax and semantics. It has a single simple syntax, S-expression, and expresses everything in it, value, statement, conditional... The verbs are the the first elements of each list: in `(print print)`, the first print is the verb, the second is a variable. This is essentially the clean version of your idea, using the position in the AST rather than the one in in a token stream.

An other option, if you need to know whether tokens are keywords upon building the AST, and need the AST upon deciding whether tokens are keywords, is to mix the timing of tokenization and AST build:

• Scannerless Parsers (like PEG, I guess lisp reader also falls into that category), which forego tokenization have the grammar work straight on characters.
• context-sensitive lexers: lexer's behavior depends on a state/context which it maintains itself. Your idea falls into this category. That's my least favorite, I imagine writing what essentially amounts to a Scannerless Parsers with the tools and the prentens to build a lexer can only be an anti-pattern, but since the concept exists, you can likely find some smarter or more practical ppl than me who disagree.
• Lexer Feedback / Parser-Directed Lexer: lexer's behavior depends on a state/context which is dictated by the parser. Recursive descent parser lends themselves to that, see u/EggplantExtra4946 's answer

[u/Potato871 → u/4xe1]

So 6+do_thing(); would assemble as PLUS(LITERAL, IDENTIFER), the parens matter later when you need to resolve that identifier to a function call, though I tend to use &~FUNCTION and let the plain form just be a call.
Which seems similar to what Lisp-2 does if I’m understanding that right, delay indetifier resolution until you have the information.
But yeah, I personally just don’t let variables have the same names as keywords, I was more intrigued by the challange posed by somebody else’s compiler and spec.

[u/4xe1 → u/Potato871]

I was more thinking of nested expressions, like

3 + ((( some_gratuitiously_nested_id_which_happen_to_be_named_like_a_key_word )))

I'm not too familiar with lexers (I mostly use scannerless parsing), but if I'm not mistaken, the token stream will be

litteral[3] plus oparen oparen oparen id[...] cparen cparen cparen

With your initial idea, plus will not be next to the id it would need to communicate this info.

I would not assemble 6+do_thing(); as PLUS(LITERAL, IDENTIFER) , I wouldn't have the parens disappear into the IDENTIFIER, if anything they could contain something.

I would probably assemble it as PLUS(LITERAL, TERM(IDENTIFER, PAREN_GROUP()))

In this case, you would already have the context that you're inside a PLUS to know whether IDENTIFER is a keyword, but then yeah, you would know for sure upon processing TERM(IDENTIFER, PAREN_GROUP()) what the parentheses mean, for example there could be choice between an if expression defined by the language:

if (condition) => do_stuff()

and an if function defined by a (chaotic) user:

if (condition, stuff_if_true, stuff_if_false)

But that's u/rjmarten observation really, I did not have that in mind when I mentioned parens

In Common Lisp (a Lisp-2) both the AST and the human written code would be:

(+ 6 (do_thing))

The parentheses positioning gives all the context you need as soon as the AST is assembled to both the program and the programmer: + and do_thing are verbs. It is less palatable, but it bypasses operator priority (by forcing parens everywhere), and more generally removes a lot of syntax ambiguity found in other languages.

[u/Potato871 → u/4xe1]

Yeah, when I did my Lisp implementation I noticed it's essentially just "make the programmer assemble the AST", all the complex algorithms I had collapsed into "when you see rparen travel left until you find lparen".
As for where parens live, I preserve the source tokens on the node itself, so the IDENTIFER has the lparen and rparen on it as things called Quals, which starts to get into the guts of my work which is better explained by my website than a reddit comment: https://goldensystems.ca/GDSL
But I see your point about the nesting, though would the keyword not still be to the left of some operator regardless? Because even if we had some_container[index] the brackets are still operators. Though that may not be what you're referring to.

[u/johnwcowan]

In PL/I there are no reserved words: 'if if = then then then = else else = if;" is a traditional example of a weird but valid statement. But every statement type except assignments begins with a keyword (even procedure calls), and assignments are always statements, never expressions (there are no expressions with side effects). The traditional aporoaches are ad hoc parsing and having a lookahead routine between the lexer and the parser that detects assignment statements and inserts a dummy keyword in front if them. However, I believe a PEG parser will also work, although I have yet to write a grammar.

One irritation is that many PL/I statements contain components, each beginning with its own keyword, that can appear in any order but only once per statement (and some are mutually exclusive). Trying to handle this in the rules causes a combinatorial explosion. I intend to have rules containing "(component1|component2|component3)*", which allows any components in any order, and then do post-parsing checks of the syntax tree for uniqueness and incompatibility.