/ellerre

An LR grammar automata generator (yet to be completed)

Primary LanguageC++GNU General Public License v3.0GPL-3.0

EllErre - An LR automata generator

EllErre is designed to be an LR automata generator, with the following algorithms:

  • [X] First Set
  • [X] Follow Set
  • [X] LR(0) automata / SLR(1) automata
  • [X] LR(1) automata
  • [X] LALR(1) automata
  • [X] GraphViz automata representation
  • [X] Mark initial and end states in the automata
  • [X] Step by Step GraphViz automata representation for LR0/LR1
  • [ ] Step by Step GraphViz automata representation for LALR1
  • [ ] Detect shift/reduce and reduce/reduce conflicts
  • [ ] LR Analysis for a given input

It is current in development.

For now, it calculates the First/Follow sets, the LR(0), LR(1) and LALR(1) automatas for a given grammar.

Installation & Compilation

sudo apt-get install git cmake build-essential flex bison libfl-dev;
git clone https://github.com/schnorr/ellerre.git ; mkdir -p ellerre/b ; cd ellerre/b ; cmake .. ; make
  • If you want to visualize the automatas with graphviz
sudo apt-get install graphviz

Compilation only

mkdir -p build ; cd build ; cmake .. ; make
-- The C compiler identification is GNU 7.3.0
-- The CXX compiler identification is GNU 7.3.0
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Found FLEX: /usr/bin/flex (found version "2.6.4") 
-- Found BISON: /usr/bin/bison (found version "3.0.4") 
-- Configuring done
-- Generating done
-- Build files have been written to: /tmp/ellerre/build
[ 11%] [BISON][parser] Building parser with bison 3.0.4
[ 22%] [FLEX][scanner] Building scanner with flex 2.6.4
Scanning dependencies of target ellerre
[ 33%] Building CXX object CMakeFiles/ellerre.dir/src/main.cc.o
[ 44%] Building CXX object CMakeFiles/ellerre.dir/src/symbol.cc.o
[ 55%] Building CXX object CMakeFiles/ellerre.dir/src/rule.cc.o
[ 66%] Building CXX object CMakeFiles/ellerre.dir/src/grammar.cc.o
[ 66%] [BISON][parser] Building parser with bison 3.0.4
[ 77%] Building CXX object CMakeFiles/ellerre.dir/scanner.cc.o
[ 88%] Building CXX object CMakeFiles/ellerre.dir/parser.cc.o
[100%] Linking CXX executable ellerre
[100%] Built target ellerre

Execution

First and Follow

cd build
./firstfollow < ../examples/ex1.ee
Grammar with 3 rules and 4 symbols (2 non-terminals):
S => A A 
A => a A 
A => b 

First sets:
S -- b a 
A -- b a 

Follow sets:
S -- $ 
A -- $ b a

LR(0) automata

cd build
./lr0 < ../examples/ex1.ee
Grammar with 4 rules and 4 symbols (2 non-terminals):
S' ⇒ S 
S ⇒ A A 
A ⇒ a A 
A ⇒ b 

LR0 item set:
S' ⇒ • S 
S' ⇒ S • 
S ⇒ • A A 
S ⇒ A • A 
S ⇒ A A • 
A ⇒ • a A 
A ⇒ a • A 
A ⇒ a A • 
A ⇒ • b 
A ⇒ b • 

LR0 automata:
State 0:
S' ⇒ • S 
---------------
S ⇒ • A A 
A ⇒ • a A 
A ⇒ • b 
Transitions: 
S ---> 1
A ---> 2
b ---> 3
a ---> 4

State 1:
S' ⇒ S • 
---------------

State 2:
S ⇒ A • A 
---------------
A ⇒ • a A 
A ⇒ • b 
Transitions: 
A ---> 5
b ---> 3
a ---> 4

State 3:
A ⇒ b • 
---------------

State 4:
A ⇒ a • A 
---------------
A ⇒ • a A 
A ⇒ • b 
Transitions: 
A ---> 6
b ---> 3
a ---> 4

State 5:
S ⇒ A A • 
---------------

State 6:
A ⇒ a A • 
---------------

LR(1) automata

cd build
./lr1  < ../examples/ex1.ee
Grammar with 4 rules and 4 symbols (2 non-terminals):
S' => S 
S => A A 
A => a A 
A => b 

First set: 
S -- b a 
A -- b a 
S' -- b a 

Follow set: 
S -- $ 
A -- $ b a 
S' -- $ 

LR1 item set:
S' => • S , $
S' => S • , $
S => • A A , $
S => A • A , $
S => A A • , $
A => • a A , $
A => • a A , b
A => • a A , a
A => a • A , $
A => a • A , b
A => a • A , a
A => a A • , $
A => a A • , b
A => a A • , a
A => • b , $
A => • b , b
A => • b , a
A => b • , $
A => b • , b
A => b • , a

LR1 automata:
State 0:
S' => • S , $
---------------
S => • A A , $
A => • a A , b
A => • a A , a
A => • b , b
A => • b , a
Transitions: 
S ---> 1
A ---> 2
b ---> 3
a ---> 4

State 1:
S' => S • , $
---------------

State 2:
S => A • A , $
---------------
A => • a A , $
A => • b , $
Transitions: 
A ---> 5
b ---> 6
a ---> 7

State 3:
A => b • , b
A => b • , a
---------------

State 4:
A => a • A , b
A => a • A , a
---------------
A => • a A , b
A => • a A , a
A => • b , b
A => • b , a
Transitions: 
A ---> 8
b ---> 3
a ---> 4

State 5:
S => A A • , $
---------------

State 6:
A => b • , $
---------------

State 7:
A => a • A , $
---------------
A => • a A , $
A => • b , $
Transitions: 
A ---> 9
b ---> 6
a ---> 7

State 8:
A => a A • , b
A => a A • , a
---------------

State 9:
A => a A • , $
---------------

LALR(1) automata

cd build
./lalr1  < ../examples/ex1.ee
Grammar with 4 rules and 4 symbols (2 non-terminals):
S' => S 
S => A A 
A => a A 
A => b 

First set: 
S -- b a 
A -- b a 
S' -- b a 

Follow set: 
S -- $ 
A -- $ b a 
S' -- $ 

LALR1 item set:
S' => • S , $
S' => S • , $
S => • A A , $
S => A • A , $
S => A A • , $
A => • a A , $
A => • a A , b
A => • a A , a
A => a • A , $
A => a • A , b
A => a • A , a
A => a A • , $
A => a A • , b
A => a A • , a
A => • b , $
A => • b , b
A => • b , a
A => b • , $
A => b • , b
A => b • , a

LALR1 automata:
State 0:
S' => • S , $
---------------
S => • A A , $
A => • a A , b
A => • a A , a
A => • b , b
A => • b , a
Transitions: 
S ---> 1
A ---> 2
b ---> 3
a ---> 4

State 1:
S' => S • , $
---------------

State 2:
S => A • A , $
---------------
A => • a A , $
A => • b , $
Transitions: 
A ---> 5
b ---> 3
a ---> 4

State 3:
A => b • , $
A => b • , b
A => b • , a
---------------

State 4:
A => a • A , $
A => a • A , b
A => a • A , a
---------------
A => • a A , $
A => • a A , b
A => • a A , a
A => • b , $
A => • b , b
A => • b , a
Transitions: 
A ---> 6
b ---> 3
a ---> 4

State 5:
S => A A • , $
---------------

State 6:
A => a A • , $
A => a A • , b
A => a A • , a
---------------

Generating the visual representation of the automata

Each parser execution from EllErre generate a .dot file after its execution. The dot files are named after its parsing algorithm (LR0.dot, LR1.dot, and LALR1.dot).

This files can be used by tools like graphviz to generate a visual representation of the given LR automata.

Example

Running the example

The following execution generates the “LR0.dot” file, which describes the automata in the using the .dot syntax.

cd build
./lr0 < ../examples/ex1.ee >> /dev/null
cat LR0.dot
digraph g { graph [fontsize=30 labelloc="t" label="" splines=true overlap=false rankdir = "LR"]; ratio = auto;
	"state0" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
		<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #0</font></td></tr>
		<tr><td align="left" port="r0"><font face="bold">S' ⇒ • S 
</font></td></tr>
		<tr><td align="left" port="r1"><font color="gray25" face="bold">S ⇒ • A A 
</font></td></tr>
		<tr><td align="left" port="r2"><font color="gray25" face="bold">A ⇒ • a A 
</font></td></tr>
		<tr><td align="left" port="r3"><font color="gray25" face="bold">A ⇒ • b 
</font></td></tr>
	</table>>];

	"state1" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
		<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #1</font></td></tr>
		<tr><td align="left" port="r0"><font face="bold">S' ⇒ S • 
</font></td></tr>
	</table>>];

	"state2" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
		<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #2</font></td></tr>
		<tr><td align="left" port="r0"><font face="bold">S ⇒ A • A 
</font></td></tr>
		<tr><td align="left" port="r1"><font color="gray25" face="bold">A ⇒ • a A 
</font></td></tr>
		<tr><td align="left" port="r2"><font color="gray25" face="bold">A ⇒ • b 
</font></td></tr>
	</table>>];

	"state3" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
		<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #3</font></td></tr>
		<tr><td align="left" port="r0"><font face="bold">A ⇒ b • 
</font></td></tr>
	</table>>];

	"state4" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
		<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #4</font></td></tr>
		<tr><td align="left" port="r0"><font face="bold">A ⇒ a • A 
</font></td></tr>
		<tr><td align="left" port="r1"><font color="gray25" face="bold">A ⇒ • a A 
</font></td></tr>
		<tr><td align="left" port="r2"><font color="gray25" face="bold">A ⇒ • b 
</font></td></tr>
	</table>>];

	"state5" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
		<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #5</font></td></tr>
		<tr><td align="left" port="r0"><font face="bold">S ⇒ A A • 
</font></td></tr>
	</table>>];

	"state6" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
		<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #6</font></td></tr>
		<tr><td align="left" port="r0"><font face="bold">A ⇒ a A • 
</font></td></tr>
	</table>>];

state0 -> state1[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "S" ];
state0 -> state2[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "A" ];
state0 -> state3[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "b" ];
state0 -> state4[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "a" ];
state2 -> state5[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "A" ];
state2 -> state3[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "b" ];
state2 -> state4[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "a" ];
state4 -> state6[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "A" ];
state4 -> state3[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "b" ];
state4 -> state4[ penwidth = 3 fontsize = 22 fontcolor = "black" label = "a" ];
}

Generating the image

cd build
dot -Tpng LR0.dot -o LR0_output.png

./examples/LR0_output.png

EllErre web app

Alternatively, you can use: https://ellerre.herokuapp.com/

There, you can input a .dot file that defines a grammar or textually input your grammar, separating each line by a “;” . You can also download the visualizations generated.

The application was created using the Shiny package for R, and the source code is available in: ./ellerre-web

EllErre step-by-step visualization for LR0 and LR1

The LR0 and LR1 execution generate a file “LR0-step.dot” or “LR1-step.dot”, which is used by the Python script for the step-by-step visualization. It was created with Python 3.7.5.

Install the Python libraries needed (suggestion to use a conda environment):

conda create --name ellerre-env python=3.7.3
conda activate ellerre-env

sudo apt-get install graphviz graphviz-dev
pip install pygraphviz
pip install tk
pip install Pillow

To launch the Python script, you can input the step .dot file or load it using the GUI menu. You can also save the generated images step by step using the menu -> File option.

python run-steps.py build/LR0-steps.dot

The program renders the step files using the .dot type, with positions set automatically. You can use fixed nodes position by passing the fdp argument to the execution, as follows.

python run-steps.py build/LR0-steps.dot fdp

Citation

If you use the EllErre information, please cite as:

@software{ellerre,
title = {EllErre: an LR automata generator},
author = {Schnorr, L. M. and Miletto, M. C. and Solórzano A. L. V.},
year = 2020,
url = {https://github.com/schnorr/ellerre}
}

[Software] L. M. Schnorr, M. C. Miletto, and A. L. V. Solórzano, EllErre: an LR automata generator, 2020. URL: https://github.com/schnorr/ellerre