Skip to main content

Parsing Toys

Python bindings for Parsing Toys - an educational tool for visualizing Context-Free Grammar (CFG) parsing algorithms.

Installation

pip install sp-parsing-toys

Usage

Context-Free Grammar

from parsing_toys import ContextFreeGrammar

# Parse a grammar
cfg = ContextFreeGrammar()
cfg.parse("""
    E -> E + T | T
    T -> T * F | F
    F -> ( E ) | id
""")

print(cfg)

# Get terminals and non-terminals
print("Terminals:", cfg.terminals())
print("Non-terminals:", cfg.non_terminals())

Left Factoring & Left Recursion Elimination

from parsing_toys import ContextFreeGrammar

cfg = ContextFreeGrammar()
cfg.parse("""
    S -> a B | a C
    B -> b
    C -> c
""")

cfg.left_factoring()
print("After left factoring:")
print(cfg)

FIRST and FOLLOW Sets

from parsing_toys import ContextFreeGrammar

cfg = ContextFreeGrammar()
cfg.parse("""
    E -> T E'
    E' -> + T E' | ε
    T -> F T'
    T' -> * F T' | ε
    F -> ( E ) | id
""")

ff = cfg.compute_first_and_follow_set()
for i in range(ff.size()):
    symbol = ff.symbol_at(i)
    print(f"{symbol}:")
    print(f"  FIRST: {ff.get_first_set(symbol)}")
    print(f"  FOLLOW: {ff.get_follow_set(symbol)}")

LL(1) Parsing

from parsing_toys import ContextFreeGrammar

cfg = ContextFreeGrammar()
cfg.parse("""
    E -> T E'
    E' -> + T E' | ε
    T -> F T'
    T' -> * F T' | ε
    F -> ( E ) | id
""")

table = cfg.compute_ll1_table()
print("Has conflict:", table.has_conflict())

steps = table.parse("id + id * id")
print(steps)

LR Parsing (LR(0), SLR(1), LR(1), LALR(1))

from parsing_toys import ContextFreeGrammar

cfg = ContextFreeGrammar()
cfg.parse("""
    E -> E + T | T
    T -> T * F | F
    F -> ( E ) | id
""")

# SLR(1) parsing
automaton = cfg.compute_slr1_automaton()
table = cfg.compute_slr1_action_goto_table(automaton)

print("Has conflict:", table.has_conflict())

steps = table.parse("id + id * id")
print(steps)

# Get parse tree
if table.parse_tree:
    svg = table.parse_tree.to_svg()

CYK Parsing

from parsing_toys import ContextFreeGrammar

cfg = ContextFreeGrammar()
cfg.parse("""
    S -> A B
    A -> a
    B -> b
""")

# Convert to Chomsky Normal Form
cfg.to_chomsky_normal_form()
print("Is CNF:", cfg.is_chomsky_normal_form())

# Parse using CYK algorithm
result = cfg.cyk_parse("a b")
print("Accepted:", result.accepted)

Regular Expressions (NFA/DFA)

from parsing_toys import RegularExpression

re = RegularExpression()
re.parse("(a|b)*abb")

# Convert to NFA
nfa = re.to_nfa()
nfa_graph = RegularExpression.to_nfa_graph(nfa)
print("NFA states:", nfa_graph.size())

# Convert to DFA
dfa = RegularExpression.to_dfa(nfa)
dfa_graph = RegularExpression.to_dfa_graph(dfa)
print("DFA states:", dfa_graph.size())

# Minimize DFA
min_dfa = RegularExpression.to_min_dfa(dfa)
min_dfa_graph = RegularExpression.to_dfa_graph(min_dfa)
print("Minimized DFA states:", min_dfa_graph.size())

# Generate SVG visualization
svg = nfa_graph.to_svg()

API Reference

ContextFreeGrammar

  • parse(s: str) -> bool: Parse a grammar string
  • error_message() -> str: Get error message if parsing failed
  • terminals() -> List[str]: Get all terminals
  • non_terminals() -> List[str]: Get all non-terminals
  • left_factoring(expand: bool = False): Perform left factoring
  • left_recursion_elimination() -> bool: Eliminate left recursion
  • compute_first_and_follow_set() -> FirstAndFollowSet: Compute FIRST and FOLLOW sets
  • compute_ll1_table() -> MTable: Compute LL(1) parsing table
  • compute_lr0_automaton() -> FiniteAutomaton: Compute LR(0) automaton
  • compute_lr0_action_goto_table(automaton) -> ActionGotoTable: Compute LR(0) ACTION/GOTO table
  • compute_slr1_automaton() -> FiniteAutomaton: Compute SLR(1) automaton
  • compute_slr1_action_goto_table(automaton) -> ActionGotoTable: Compute SLR(1) ACTION/GOTO table
  • compute_lr1_automaton() -> FiniteAutomaton: Compute LR(1) automaton
  • compute_lr1_action_goto_table(automaton) -> ActionGotoTable: Compute LR(1) ACTION/GOTO table
  • compute_lalr1_automaton() -> FiniteAutomaton: Compute LALR(1) automaton
  • compute_lalr1_action_goto_table(automaton) -> ActionGotoTable: Compute LALR(1) ACTION/GOTO table
  • to_chomsky_normal_form(): Convert grammar to CNF
  • is_chomsky_normal_form() -> bool: Check if grammar is in CNF
  • cyk_parse(s: str) -> CYKTable: Parse using CYK algorithm

RegularExpression

  • parse(pattern: str) -> bool: Parse a regular expression
  • error_message() -> str: Get error message if parsing failed
  • to_nfa() -> NFAState: Convert to NFA
  • to_dfa(nfa: NFAState) -> DFAState: Convert NFA to DFA (static)
  • to_min_dfa(dfa: DFAState) -> DFAState: Minimize DFA (static)
  • to_nfa_graph(nfa: NFAState) -> NFAGraph: Convert NFA to graph (static)
  • to_dfa_graph(dfa: DFAState) -> DFAGraph: Convert DFA to graph (static)

License

MIT License

Metadata

Release files for parsing-toys 1.2.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for parsing-toys 1.2.0
File Size Uploaded Provenance Actions
parsing_toys-1.2.0.tar.gz 36.2 kB Without provenance Details for parsing_toys-1.2.0.tar.gz

Release files / parsing_toys-1.2.0.tar.gz

Download URL parsing_toys-1.2.0.tar.gz
Size 36.2 kB
Tags Source
SHA-256 checksum
How to use checksums
4f7e1b6ea6184f02e8419570d041e810556f3a2f8b7b1df09e4315b287213c0e
BLAKE2b-256 checksum
How to use checksums
7767e32371ac2f6951e2d47c5c0ec56a34e6292a505995f631447cec7cc7eae6
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/6.1.0 CPython/3.8.20

Security for parsing-toys 1.2.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Release history Release notifications | RSS feed

This release

1.2.0 This release

1 release file No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page