Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I construct a clean, Python like grammar in ANTLR?

Tags:

grammar

antlr

G'day!

How can I construct a simple ANTLR grammar handling multi-line expressions without the need for either semicolons or backslashes?

I'm trying to write a simple DSLs for expressions:

# sh style comments
ThisValue = 1
ThatValue = ThisValue * 2
ThisOtherValue = (1 + 2 + ThisValue * ThatValue)
YetAnotherValue = MAX(ThisOtherValue, ThatValue)

Overall, I want my application to provide the script with some initial named values and pull out the final result. I'm getting hung up on the syntax, however. I'd like to support multiple line expressions like the following:

# Note: no backslashes required to continue expression, as we're in brackets
# Note: no semicolon required at end of expression, either
ThisValueWithAReallyLongName = (ThisOtherValueWithASimilarlyLongName
                               +AnotherValueWithAGratuitouslyLongName)

I started off with an ANTLR grammar like this:

exprlist
    : ( assignment_statement | empty_line )* EOF!
    ;
assignment_statement
    : assignment NL!?
    ;
empty_line
    : NL;
assignment
    : ID '=' expr
    ;

// ... and so on

It seems simple, but I'm already in trouble with the newlines:

warning(200): StackOverflowQuestion.g:11:20: Decision can match input such as "NL" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input

Graphically, in org.antlr.works.IDE:

Decision Can Match NL Using Multiple Alternatives http://img.skitch.com/20090723-ghpss46833si9f9ebk48x28b82.png

I've kicked the grammar around, but always end up with violations of expected behavior:

  • A newline is not required at the end of the file
  • Empty lines are acceptable
  • Everything in a line from a pound sign onward is discarded as a comment
  • Assignments end with end-of-line, not semicolons
  • Expressions can span multiple lines if wrapped in brackets

I can find example ANTLR grammars with many of these characteristics. I find that when I cut them down to limit their expressiveness to just what I need, I end up breaking something. Others are too simple, and I break them as I add expressiveness.

Which angle should I take with this grammar? Can you point to any examples that aren't either trivial or full Turing-complete languages?

like image 383
Garth Kidd Avatar asked Jul 23 '09 03:07

Garth Kidd


People also ask

What is ANTLR Python?

ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.

What is an ANTLR grammar?

ANTLR (ANother Tool for Language Recognition) is a tool for processing structured text. It does this by giving us access to language processing primitives like lexers, grammars, and parsers as well as the runtime to process text against them. It's often used to build tools and frameworks.

What kind of parser is ANTLR?

ANTLR is a powerful parser generator that you can use to read, process, execute, or translate structured text or binary files. It's widely used in academia and industry to build all sorts of languages, tools, and frameworks. Twitter search uses ANTLR for query parsing, with over 2 billion queries a day.


1 Answers

I would let your tokenizer do the heavy lifting rather than mixing your newline rules into your grammar:

  • Count parentheses, brackets, and braces, and don't generate NL tokens while there are unclosed groups. That'll give you line continuations for free without your grammar being any the wiser.

  • Always generate an NL token at the end of file whether or not the last line ends with a '\n' character, then you don't have to worry about a special case of a statement without a NL. Statements always end with an NL.

The second point would let you simplify your grammar to something like this:

exprlist
    : ( assignment_statement | empty_line )* EOF!
    ;
assignment_statement
    : assignment NL
    ;
empty_line
    : NL
    ;
assignment
    : ID '=' expr
    ;
like image 147
John Kugelman Avatar answered Nov 05 '22 12:11

John Kugelman