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 stringerror_message() -> str: Get error message if parsing failedterminals() -> List[str]: Get all terminalsnon_terminals() -> List[str]: Get all non-terminalsleft_factoring(expand: bool = False): Perform left factoringleft_recursion_elimination() -> bool: Eliminate left recursioncompute_first_and_follow_set() -> FirstAndFollowSet: Compute FIRST and FOLLOW setscompute_ll1_table() -> MTable: Compute LL(1) parsing tablecompute_lr0_automaton() -> FiniteAutomaton: Compute LR(0) automatoncompute_lr0_action_goto_table(automaton) -> ActionGotoTable: Compute LR(0) ACTION/GOTO tablecompute_slr1_automaton() -> FiniteAutomaton: Compute SLR(1) automatoncompute_slr1_action_goto_table(automaton) -> ActionGotoTable: Compute SLR(1) ACTION/GOTO tablecompute_lr1_automaton() -> FiniteAutomaton: Compute LR(1) automatoncompute_lr1_action_goto_table(automaton) -> ActionGotoTable: Compute LR(1) ACTION/GOTO tablecompute_lalr1_automaton() -> FiniteAutomaton: Compute LALR(1) automatoncompute_lalr1_action_goto_table(automaton) -> ActionGotoTable: Compute LALR(1) ACTION/GOTO tableto_chomsky_normal_form(): Convert grammar to CNFis_chomsky_normal_form() -> bool: Check if grammar is in CNFcyk_parse(s: str) -> CYKTable: Parse using CYK algorithm
RegularExpression
parse(pattern: str) -> bool: Parse a regular expressionerror_message() -> str: Get error message if parsing failedto_nfa() -> NFAState: Convert to NFAto_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)
| 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.