Skip to main content

Parser Glossary

Abbr.WordDesc
BNFBackus–Naur form巴科斯范式 - 1959 John Backus
EBNFextended BNF扩展巴科斯范式 - ISO-14977
DFADeterministic finite automaton确定有限状态自动机
NFANondeterministic finite automaton非确定有限状态自动机
CFGContext free grammar上下文无关语法
TDPLTop-Down Parsing Language
LL(k)Left-to-right, Leftmost derivationtop-down - 1970s
LLRLL-regular
LRLeft-to-right, Rightmost derivation in reversebottom-up - 1965 Donald Knuth
DCFGDeterministic Context Free Grammar
PEGParsing expression grammar解析表达文法 - 2004 Bryan Ford
ANTLRANother Tool for Language Recognition
LALRLook-Ahead LR parser简化版的 LR
SLR
Canonical LR(1)
Minimal LR(1)
GLR
RPNReverse Polish notation
encn
grammar语法
syntax语法
semantics语义
expression表达式
term

Left recursion

a and b and c

{
"type": "and",
// left
"left": {"type": "and", "left": {"term": "a"}, "right": {"term": "b"}},
//
"right": {"term": "c"}
}