Giter Site home page Giter Site logo

unrealeugene / lalr-parser-generator Goto Github PK

View Code? Open in Web Editor NEW
0.0 1.0 0.0 104 KB

An implementation of LALR(1) parser generator in Java with synthesized attributes and parsing automaton visualization

Java 87.12% ANTLR 2.80% FreeMarker 10.07%
java lalr parser-generator

lalr-parser-generator's Introduction

LARL(1) Parser Generator

Java implementation of LALR(1) parser generator with supported synthesized attributes written as a home assignment for parsing course in ITMO University.

Features

  • Generate parsers for LALR(1) grammars
  • Parsing automaton visualization
  • Regular expressions in tokens
  • Synthesized attributes
  • TODO: Ambiguous grammar check

Examples

Consider a simple grammar for balanced bracket sequences:

S0 -> S;

S  -> '(' S ')' S;
S  -> ε;

The following parsing automaton can be obtained from this grammar:

Grammar parsing automaton

The following AST can be built from the input (())():

Abstract syntax tree

An example of the more complex grammar for arithmetic expressions with usage of synthesized attributes to calculate expression value:

E0 [long val] -> E {val = $0.val;};

E [long val]  -> E '+' T {val = $0.val + $2.val;} | E '-' T {val = $0.val - $2.val;} | T {val = $0.val;};
T [long val]  -> T '*' F {val = $0.val * $2.val;} | T '/' F {val = $0.val / $2.val;} | F {val = $0.val;};
F [long val]  -> P '**' F {val = (long) Math.pow($0.val, $2.val);} | P {val = $0.val;};
P [long val]  -> r'[+-]?([1-9][0-9]*|0)' {val = Long.parseLong($0);} | '(' E ')' {val = $1.val;};

@skip r'[ \n\r\t]+';

Usage

To generate LALR(1) parser based on a context free grammar first you need to specify grammar productions in form described in grammar for grammars. After that the GenerateParser class needs to be called with path to grammar as its first argument and, possibly, more optional arguments:

-o <path>: output path for generated sources (required)
-i <path>: output path for parsing automaton images (by default images are not generated)
-n <name>: grammar name used as generated class prefix (default: grammar file name)
-p <name>: generated classes package (default: empty)

After a successful execution three Java classes will be generated in specified output path: Lexer, Parser and Token.

Note: If you want to generate parsing automaton images, you'll need to install GraphViz and then provide a path to GraphViz executable in config.properties file.

lalr-parser-generator's People

Contributors

unrealeugene avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.