cfgrammar 0.1.2.2

Context-free grammars and parsing

cfgrammar : Context-free grammars, parsing and semantic

Table of Contents

• Main Features
• Example
• API overall graph
• Parsing example
• Abstract Syntax Tree

Main features

• Grammar properties
  • accessible and productive rules / variables
  • ε-productive rules / variables
  • reduced grammar
  • "First" and "Follow" sets
• LL1 parsing
  • computes and displays LL(1) table
  • constructs parser
• LR parsing
  • computes and displays LR(0) automaton
  • constructs LR(0), SLR(1), LALR(1) tables and parsers
• Semantic
  • parsing with semantic actions
• Abstract Syntax Tree
  • predefined semantic classes to produce AST
    • Graphviz / dot output
    • Latex + Tikz output

Example

Code :

from cfgrammar import Grammar

g = Grammar.from_string('S -> ( S ) S | a')

print(g)
print('productives variables : ', g.productive.vars)
print('Follow sets : ', g.follow)
print(g.tableLL1().to_markdown())

Output:

Grammar(
     terminals : ( ) a
     variables : S
     axiom : S
     rules : ['S → ( S ) S', 'S → a']
    )
productives variables :  {'S'}
Follow sets :  {'S': {')', '#'}}
|    | S           |
|:---|:------------|
| (  | S → ( S ) S |
| )  |             |
| a  | S → a       |
| #  |             |

API overall graph

Parsing example

from cfgrammar.builder import ParserBuilder

parser = ParserBuilder.from_dict({
    'E -> E + T ': lambda p,*_ : p.E + p.T,
    'E -> T' : lambda p,*_: p.T,
    'T -> T * F ': lambda p,*_ : p.T * p.F,
    'T -> F' : lambda p,*_: p.F,
    'F -> ( E )' : lambda p,*_ : p.E,
    'F -> 0|1|2|3|4|5|6|7|8|9' : lambda p,*_ : int(p[0])
})
print('Value: ',parser.parse('2*(4+5*(1+1))'))
print(parser.grammar)
print(parser.method)

output :

Value:  28
GrammarBase(
     terminals : ( ) * + 0 1 2 3 4 5 6 7 8 9
     variables : F E T
     axiom : E
     rules : ['E → E + T', 'E → T', 'T → T * F', 'T → F', 'F → ( E )', 'F → 0', 'F → 1', 'F → 2', 'F → 3', 'F → 4', 'F → 5', 'F → 6', 'F → 7', 'F → 8', 'F → 9']
    )
LRMethod.LALR1

Abstract Syntax Tree

Graphviz AST

Predefined semantic producing graphviz (dot) text.

from cfgrammar.semantic import GraphvizAST
display_ast  = GraphvizAST()
dot_source = parser.parse('2*(4+5*(1+1))',display_ast)

from graphviz import Source
Source(dot_source).view()

Latex AST

LatexForestAST produces latex source (needs forest latex package)

from cfgrammar.semantic import LatexForestAST
display_latex_ast  = LatexForestAST()
latex_source = parser.parse('2*(4+5*(1+1))',display_latex_ast)