No reserved words

[Korporal]

I'd like to ask if there is any inherent restriction within ANTLR that prevents it from generating a parser for a language that has no reserved words, one example of such a language is PL/I and there are probably more.

Any info appreciated.

[ericvergnaud]

According to Wikipedia, PL/I does have reserved words...
TBH not sure it's possible for a programming language to not have any

[KvanTTT]

Probably @Korporal means context keywords. These words can be either keywords or identifiers depending on context. And such words are being recognized on the parser stage, not on the lexer. SQL dialects (MySql, PL/SQL, T-SQL) have a lot of such words. The following syntax can be used for description, but semantic predicates are required:

getter
    : {_input.LT(1).getText().equals("get")}? Identifier propertyName
    ;

[Korporal]

Probably @Korporal means context keywords. These words can be either keywords or identifiers depending on context. And such words are being recognized on the parser stage, not on the lexer. SQL dialects (MySql, PL/SQL, T-SQL) have a lot of such words. The following syntax can be used for description, but semantic predicates are required:

getter
    : {_input.LT(1).getText().equals("get")}? Identifier propertyName
    ;

The recursive descent parser I developed followed the strategy outlined in this paper, written by the team lead of the compiler development team for Multics at GE:

[Korporal]

Hi, well this is interesting because I'm developing a grammar for a not-yet-existing language and it will have no reserved words. I want to distinguish too between "keywords" and "reserved words".

A keyword is a word (same lexical structure as an identifier) that also carries a meaning within the language like if or goto and so on.

A reserved word is a word that cannot be used as an identifier, it is reserved, unavailable for use as a variable or method or type name.

PL/I has no reserved words, so this is entirely valid and parsed without problem:

if then = if then
   goto else;
else
   return goto;

Nobody would write stuff like that but the language lets you, it does not care. The reason it lets you is that this design means new keywords can be be added in the future without issue, because even if the new keyword had been used as an identifier by someone it matters not.

I just have no idea if these kinds of parsing tools can generate parsers for these kinds of languages. I developed a compiler for PL/I several decades ago and had no access to tools like this. So I "hand crafted" a recursive descent parser written in C. This worked fine and was in fact able to generate linkable COFF binaries for 32-bit Windows NT (as it was called back then).

But I know this is very uncommon in language design and so tools may simply not bother with the problem.

[ericvergnaud]

Are you looking to build a PL/I parser in a supported language target (such as Java, C#, C++, Python) or build a parser generator for PL/I (i.e. a new ANTLR language target) ?

[Korporal]

Are you looking to build a PL/I parser in a supported language target (such as Java, C#, C++, Python) or build a parser generator for PL/I (i.e. a new ANTLR language target) ?

Neither, I'm curious about developing a new grammar that has no reserved words, this grammar will - not immediately - be developed so that it can represent all that C# can do.

So, I'm developing a new grammar that could eventually replace the C# grammar, and one difference is that it would have no reserved words.

So I'm just curious as to whether ANTLR can be configured to consume some grammar definition where that grammar does not reserve words.

I can craft the lexical analyzer and parser "by hand" but don't want to avoid using a tool if that tool can do the work for me.

[ericvergnaud]

Back to your previous example it’s trivial for a grammar to accept a keyword as an identifier: IF: ‘if’; IDENTIFIER: [a-z]+; some_rule: IF identifier_or_keyword …; identifier_or_keyword: IDENTIFIER | IF; In that sense, you can build a grammar with no reserved words.

…

Le 28 oct. 2021 à 00:22, Hugh Gleaves ***@***.***> a écrit : Are you looking to build a PL/I parser in a supported language target (such as Java, C#, C++, Python) or build a parser generator for PL/I (i.e. a new ANTLR language target) ? Neither, I'm curious about developing a new grammar that has no reserved words, this grammar will - not immediately - be developed so that it can represent all that C# can do. So, I'm developing a new grammar that could eventually replace the C# grammar, and one difference is that it would have no reserved words. So I'm just curious as to whether ANTLR can be configured to consume some grammar definition where that grammar does not reserve words. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#3321 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAZNQJBAYUDM3PAKFRLLAV3UJB3TFANCNFSM5GYIUWIQ>.

[RossPatterson]

The Rexx language doesn't have reserved words - similar to PL/I, certain words are reserved in certain contexts. There's an example grammar for it in https://github.com/antlr/grammars-v4/tree/master/rexx. It works just fine.

[kaby76]

I tried to reproduce the rexx perf problem -- I can't. Here are my changes to the current grammar. I've also included code for the CSharp target so that I can run my grammar analysis tools on this. I also renamed the temp-examples in the pom (which tells the tools how to run tests on the grammar) to "examples/" so there is some testing. Currently, the generated parser for the grammar is not tested in the CI build!

diff --git a/rexx/RexxParser.g4 b/rexx/RexxParser.g4
index eec877a4..ad9293fd 100644
--- a/rexx/RexxParser.g4
+++ b/rexx/RexxParser.g4
@@ -115,7 +115,66 @@ drop_                       :   KWD_DROP variable_list ;
     vref                    :   BR_O var_symbol BR_C ;
     var_symbol              :   VAR_SYMBOL
                             |   SPECIAL_VAR
+			    | all_keywords
                             ;
+
+all_keywords: KWD_ADDRESS
+| KWD_ARG
+| KWD_BY
+| KWD_CALL
+| KWD_DIGITS
+| KWD_DO
+| KWD_DROP
+| KWD_ELSE
+| KWD_END
+| KWD_ENGINEERING
+| KWD_ERROR
+| KWD_EXIT
+| KWD_EXPOSE
+| KWD_EXTERNAL
+| KWD_FAILURE
+| KWD_FOR
+| KWD_FOREVER
+| KWD_FORM
+| KWD_FUZZ
+| KWD_HALT
+| KWD_IF
+| KWD_INTERPRET
+| KWD_ITERATE
+| KWD_LEAVE
+| KWD_NAME
+| KWD_NOP
+| KWD_NOVALUE
+| KWD_NUMERIC
+| KWD_OFF
+| KWD_ON
+| KWD_OPTIONS
+| KWD_OTHERWISE
+| KWD_PARSE
+| KWD_PROCEDURE
+| KWD_PULL
+| KWD_PUSH
+| KWD_QUEUE
+| KWD_RETURN
+| KWD_SAY
+| KWD_SCIENTIFIC
+| KWD_SELECT
+| KWD_SIGNAL
+| KWD_SOURCE
+| KWD_SYNTAX
+| KWD_THEN
+| KWD_TO
+| KWD_TRACE
+| KWD_UNTIL
+| KWD_UPPER
+| KWD_VALUE
+| KWD_VAR
+| KWD_VERSION
+| KWD_WHEN
+| KWD_WHILE
+| KWD_WITH
+;
+
 exit_                       :   KWD_EXIT expression? ;
 interpret_                  :   KWD_INTERPRET expression ;
 iterate_                    :   KWD_ITERATE var_symbol? ;
@@ -263,13 +322,7 @@ power_expression            :   prefix_expression ( POW prefix_expression )* ;
       hex_string            :   HEX_STRING ;
       string                :   STRING ;
       function_             :   function_name function_parameters ;
-        function_name       :   KWD_ADDRESS
-                            |   KWD_ARG
-                            |   KWD_DIGITS
-                            |   KWD_FORM
-                            |   KWD_FUZZ
-                            |   KWD_TRACE
-                            |   KWD_VALUE
-                            |   taken_constant
+        function_name       :   taken_constant
+				| all_keywords
                             ;
         function_parameters :   BR_O expression_list? BR_C ;
diff --git a/rexx/pom.xml b/rexx/pom.xml
index a30cd2fe..7e17dea9 100644
--- a/rexx/pom.xml
+++ b/rexx/pom.xml
@@ -46,7 +46,7 @@
 					<showTree>false</showTree>
 					<entryPoint>file_</entryPoint>
 					<grammarName>Rexx</grammarName>
-					<exampleFiles>temp-examples/</exampleFiles>
+					<exampleFiles>examples/</exampleFiles>
 					<testFileExtension></testFileExtension>
 					<packageName></packageName>
 				</configuration>

But, even before this change, there is an ambiguity for input "binary_good1 = '1'b
" in single_instruction, in choosing between assignment and command_ => expression => and_expression => comparison. The way expressions are written is an "anti-pattern" for Antlr in itself not even considering assignment. But, with both involved, it will cause adaptivePredict() to run down the entire derivation chain of command_ until the end of the assignment because it's trying to find a difference based on context.

[RossPatterson]

"But, even before this change, there is an ambiguity for input "binary_good1 = '1'b
" in single_instruction, in choosing between assignment and command_ => expression => and_expression => comparison. The way expressions are written is an "anti-pattern" for Antlr in itself not even considering assignment. But, with both involved, it will cause adaptivePredict() to run down the entire derivation chain of command until the end of the assignment because it's trying to find a difference based on context._"

Thanks for pointing that out. I've opened grammars-v4 issue #2820 to address it. The order and content of the parser rules matches (almost) rule-by-rule to the ANSI standard, so if there are anti-patterns for ANTLR, I guess I'm not surprised it encounters them. I guess I'll have to eventually add an "Optimize the Rexx grammar for ANTLR4" issue, but I think I need more ANTLR experience and study before I can even express the problem well.

[RossPatterson]

I tried to reproduce the rexx perf problem -- I can't.

Apparently some intervening change between grammars-v4/master and the tip of my working copy set up a condition where this seemingly-innocuous change causes the performance problem. Since seeing your reply, I have attempted to reproduce the problem on a clean branch from master with just the add-all-64-keywords changes, and I cannot. Obviously, I should have done that before posting. :-(

It's time for me to isolate the changes in my working copy that set the conditions for the poor performance.

[RossPatterson]

I also renamed the temp-examples in the pom (which tells the tools how to run tests on the grammar) to "examples/" so there is some testing. Currently, the generated parser for the grammar is not tested in the CI build!

Rats. I made explicit changes to make those tests function correctly in the ANTLR build system. I've opened grammars-v4 issue #2821 to address this.

[kaby76]

All okay. You're still working on this. I'll help by refactoring the expression rules in a day or two.