Light

amirhossein-hkh / lr-parser Goto Github PK

View Code? Open in Web Editor NEW

64.0 2.0 22.0 96 KB

LR Parser (LR(0), SLR(1), CLR(1) and LALR(1))

License: MIT License

Java 100.00%

lr-parser slr1 lr1 lr0 clr1 lalr-parser slr-parser parser context-free-grammar lr-parser-java

lr-parser's Introduction

LR Parser (LR(0), SLR(1), CLR(1) and LALR(1))

LR Parser is a bottom-up parser for reading grammar. There are different kinds of LR Parser which some of them are: SLR parsers, LALR parsers, Canonical LR(1) parsers.

I implemented these parsers using java with GUI to be used more conveniently. It's very simple.First you enter your context-free grammar choose the parser(LR(0), SLR(1), CLR(1) and LALR(1)). Then, you can see all the properties of the parsed grammar (Augmented Grammar, First Sets, Follow Sets, Canonical Collection, Go To Table, Action Table) by clicking on the corresponding button. Also, you can give different input and check whether grammar accepts the string or not.

here is a screenshot from the application:

lr-parser's People

Contributors

Stargazers

Watchers

lr-parser's Issues

problem in LR(0) and SLR(1)

There are some issues in the Action Table. It doesn't accept the grammar and throws Null Pointer Exception while giving
S -> A
A -> a
this grammar as input in both of the Parser. SLR(1) shows accept in the Action Table but says not accepted while displaying the input.

Problem in Grammar' s FirstSet

When processing left recursion, the function computeFirst will be in endless loop

Compiled project

Hello!
Can you add to existing project release binary, please?
Thank you!

LR1State closure must merge lookaheads of matching items

In LR1State closure method, new items are created with lookaheads. In some cases, items may be created that differ only by lookahead sets. These states must be merged together otherwise duplicate transition will be created in LR1Parser and incorrect tables are created.

Reproducing this requires a large and complicated grammar and diagnostics that show the duplicate items and transitions. That would require more time to prepare than I have so I'll just be sending over another pull request with the fix.

Missing reduce for epsilon LR0 items

The following test problem shows a missing reduce on $ (EOF) for state 0.
Grammar:
S -> a
S -> epsilon
I'll create a pull request with fix.

import util.*;
import lr0.*;
import lr1.*;
public class TestLR
{
    public static void main(String[] args) {
        String g = "S -> a\n" +
                   "S -> epsilon\n";

        LR0Parser lr0Parser = new LR0Parser(new Grammar(g));
        if (lr0Parser.parserSLR1()) {
            System.out.println(lr0Parser.actionTableStr());
            System.out.println(lr0Parser.goToTableStr());
        }
        else {
            System.out.println("parse not ok");
        }
    }
}

$ java TestLR
Rules: 
0 : S' -> S 
1 : S -> a 
2 : S -> epsilon 
Action Table : 

                a         $         
--------------------------------
|0         |  SHIFT 2|         |
--------------------------------
|1         |         | REDUCE 2|
--------------------------------
|2         |         | REDUCE 1|
--------------------------------
|3         |         |  ACCEPT |
--------------------------------

Problems with follow sets, epsilon handling, LR0 table

There are some problems with follow sets, epsilon handling, and the lr0 action table which I have been able to identify fixes for.

But before that, thank you very much for writing this code. Your code is smaller and simpler than a lot of other projects and it has helped me to learn LR parsing better.

This grammar is not handled correctly:

S -> A B
A -> a
A -> epsilon
B -> b
B -> epsilon

The following test program demonstrates incorrect tables. The proper tables are shown down below further. They can also be computed online at https://mdaines.github.io/grammophone
(just add periods to the end of rules and remove the epsilons).

import util.*;
import lr1.*;
public class TestLR
{
    public static void main(String[] args) {
        String grammarText = "S -> A B  \n" +
                             "A -> a       \n" +
                             "A -> epsilon \n" +
                             "B -> b       \n" +
                             "B -> epsilon \n";
        LR1Parser lr1Parser = new LR1Parser(new Grammar(grammarText));
        if (lr1Parser.parseCLR1()) {
            System.out.println(lr1Parser.actionTableStr());
            System.out.println(lr1Parser.goToTableStr());
        }
        else {
            System.out.println("parse not ok");
        }
    }
}

$ java TestLR
Rules:
0 : S' -> S
1 : S -> A B
2 : A -> a
3 : A -> epsilon
4 : B -> b
5 : B -> epsilon
Action Table :
                epsilon   a         b         $
----------------------------------------------------
|0         |  SHIFT 1|  SHIFT 3|         |         |
----------------------------------------------------
|1         |         |         | REDUCE 3| REDUCE 3|
----------------------------------------------------
|2         |  SHIFT 5|         |  SHIFT 7|         |
----------------------------------------------------
|3         |         |         | REDUCE 2| REDUCE 2|
----------------------------------------------------
|4         |         |         |         |  ACCEPT |
----------------------------------------------------
|5         |         |         |         | REDUCE 5|
----------------------------------------------------
|6         |         |         |         | REDUCE 1|
----------------------------------------------------
|7         |         |         |         | REDUCE 4|
----------------------------------------------------
Go TO Table :
          A     B     S
--------------------------
|0     |    2|     |    4|
--------------------------
|1     |     |     |     |
--------------------------
|2     |     |    6|     |
--------------------------
|3     |     |     |     |
--------------------------
|4     |     |     |     |
--------------------------
|5     |     |     |     |
--------------------------
|6     |     |     |     |
--------------------------
|7     |     |     |     |
--------------------------

Epsilon should not be in the action table. Also, the action table is not correct. For example in state 0 an EOF ($) is valid, and should be a reduce of A to epsilon (rule 3).

This is the correct output:

$ java TestLR
Rules:
0 : S' -> S
1 : S -> A B
2 : A -> a
3 : A -> epsilon
4 : B -> b
5 : B -> epsilon
Action Table :
                a         b         $
------------------------------------------
|0         |  SHIFT 2| REDUCE 3| REDUCE 3|
------------------------------------------
|1         |         |  SHIFT 5| REDUCE 5|
------------------------------------------
|2         |         | REDUCE 2| REDUCE 2|
------------------------------------------
|3         |         |         |  ACCEPT |
------------------------------------------
|4         |         |         | REDUCE 1|
------------------------------------------
|5         |         |         | REDUCE 4|
------------------------------------------
Go TO Table :
         A     B     S
--------------------------
|0     |    1|     |    3|
--------------------------
|1     |     |    4|     |
--------------------------
|2     |     |     |     |
--------------------------
|3     |     |     |     |
--------------------------
|4     |     |     |     |
--------------------------
|5     |     |     |     |
--------------------------

I have prepared fixes and will send over a pull request.

I want to also let you know that I plan on using this code in a new project soon. It is much appreciated that you offered an MIT license.

very helpful

love you bro

Recommend Projects

React

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

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

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

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
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.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

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

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.

amirhossein-hkh / lr-parser Goto Github PK

lr-parser's Introduction

LR Parser (LR(0), SLR(1), CLR(1) and LALR(1))

lr-parser's People

Contributors

Stargazers

Watchers

Forkers

lr-parser's Issues

Recommend Projects

Recommend Topics

Recommend Org