Git Product home page Git Product logo

ll1-parser's Introduction

LL1-Parser

LL1 parser implementation. A program to generate an LL(1) parser for a given grammar and to parse input strings.

For following grammer and input string: a+a*a+a

Output:

Grammar:

   E -> TX
   X -> +TX
   X -> ε
   T -> FY
   Y -> *FY
   Y -> ε
   F -> (E)
   F -> a

First sets: 

   E : [ '(', 'a' ]
   T : [ '(', 'a' ]
   F : [ '(', 'a' ]
   ( : [ '(' ]
   a : [ 'a' ]
   X : [ '+', 'ε' ]
   + : [ '+' ]
   Y : [ '*', 'ε' ]
   * : [ '*' ]
   ) : [ ')' ]

Follow sets: 

   E : [ '$', ')' ]
   X : [ '$', ')' ]
   T : [ '+', '$', ')' ]
   Y : [ '+', '$', ')' ]
   F : [ '*', '+', '$', ')' ]

NonTerminals: E,X,T,Y,F
Terminals: +,ε,*,(,),a

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │ + │ ε │ * │ ( │ ) │ a │ $ │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ E │   │   │   │ 1 │   │ 1 │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ X │ 2 │   │   │   │ 3 │   │ 3 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ T │   │   │   │ 4 │   │ 4 │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ Y │ 6 │   │ 5 │   │ 6 │   │ 6 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ F │   │   │   │ 7 │   │ 8 │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

┌───────────────┬───────────┬──────────┬──────────┐
│ CONSUMEDINPUT │ STACK     │ REMAIN   │ ACTION   │
├───────────────┼───────────┼──────────┼──────────┤
│               │ $,X,T     │ a+a*a+a$ │ TX       │
├───────────────┼───────────┼──────────┼──────────┤
│               │ $,X,Y,F   │ a+a*a+a$ │ FY       │
├───────────────┼───────────┼──────────┼──────────┤
│               │ $,X,Y,a   │ a+a*a+a$ │ a        │
├───────────────┼───────────┼──────────┼──────────┤
│ a             │ $,X,Y     │ +a*a+a$  │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a             │ $,X,ε     │ +a*a+a$  │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a             │ $,X       │ +a*a+a$  │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a             │ $,X,T,+   │ +a*a+a$  │ +TX      │
├───────────────┼───────────┼──────────┼──────────┤
│ a+            │ $,X,T     │ a*a+a$   │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+            │ $,X,Y,F   │ a*a+a$   │ FY       │
├───────────────┼───────────┼──────────┼──────────┤
│ a+            │ $,X,Y,a   │ a*a+a$   │ a        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a           │ $,X,Y     │ *a+a$    │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a           │ $,X,Y,F,* │ *a+a$    │ *FY      │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*          │ $,X,Y,F   │ a+a$     │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*          │ $,X,Y,a   │ a+a$     │ a        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a         │ $,X,Y     │ +a$      │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a         │ $,X,ε     │ +a$      │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a         │ $,X       │ +a$      │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a         │ $,X,T,+   │ +a$      │ +TX      │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+        │ $,X,T     │ a$       │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+        │ $,X,Y,F   │ a$       │ FY       │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+        │ $,X,Y,a   │ a$       │ a        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $,X,Y     │ $        │ Matched! │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $,X,ε     │ $        │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $,X       │ $        │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $,ε       │ $        │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $         │ $        │ ε        │
├───────────────┼───────────┼──────────┼──────────┤
│ a+a*a+a       │ $         │ $        │ Accept!  │
└───────────────┴───────────┴──────────┴──────────┘
Ans: Accept! (a+a*a+a)

ll1-parser's People

Contributors

sinakarimi7 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.