Rain's Blog

六、上下文无关文法-CFG Definition-(Context-Free Grammar(CFG), 上下文无关文法) 上下文无关文法GGG是一个四元组G=(T,N,S,P)G = (T,N,S,P)G=(T,N,S,P) TTT是终结符号（Terminal）集合，对应于词法分析器产生的词法单元 NNN是非终止符号（Non-terminal）集合 SSS是开始（start）符号(S∈N)(S \in N)(S∈N)且唯一 PPP是产生式（Production）集合 A∈N→α∈(T∪N)∗A \in N \to \alpha \in (T \cup N)^* A∈N→α∈(T∪N)∗ 头部/左部（Head）A：单个非终结符 体部/右部（Body）α\alphaα：终结符与非终结符构成的串，也可以是空串ϵ\epsilonϵ [Entended] Backus-Naur form ([E]BNF) CFG 语义 语义：上下文无关文法GGG定义了一个语言L(G)L(G)L(G) 语言是串的集合 推导 E→E+E∣E∗E∣(E)∣−E∣idE \to E ...

五、ANTLR 4 语法分析器 语法分析 二异性文法 若文法G对同一句子产生不止一棵分析树，则称G是二义的。 If-Then-Else的二异性 1234567891011121314//IfStat.g4stat : 'if' expr 'then' stat | 'if' expr 'then' stat 'else' stat | expr ;->//IfStatOpenMatched.g4stat : matched_stat | open_statmatched_stat : 'if' expr 'then' matched_stat 'else' matched_stat | expr ;open_stat : 'if' expr 'then' stat | 'if' expr 'then ...

四、自动机理论与词法分析器生成器 自动机-Automation/Automata 两大要素：状态集S 和 状态转移函数δ\deltaδ 元胞自动机-Cellular Automation/CA 根据表达/计算能力的强弱，自动机可以分为不同的层次 目标 正则表达式RE => 词法分析器 非自动性有穷自动机-NFA/Nondeteministic Finite Automaton AAA是一个五元组 A=(Σ,S,s0,δ,F)A = (\Sigma , S, s_{0},\delta,F)A=(Σ,S,s0​,δ,F): 1.字母表Σ\SigmaΣ(ϵ∉Σ)(\epsilon \notin \Sigma)(ϵ∈/​Σ) 2.有穷的状态集合SSS 3.唯一的初始状态s0∈Ss_{0} \in Ss0​∈S 4.状态转移函数$ \delta $ δ:S×(Σ∪{ϵ})→2S\delta : S \times (\Sigma \cup \lbrace \epsilon \rbrace) \to 2^S δ:S×(Σ∪{ϵ})→2S 5.接受状态集合F⊆SF \subsete ...

一、关系、关系模式和关系数据库 域 域是一组具有相同数据类型的值的集合。 笛卡尔积（Cartesian Product） 1.给定一组域D1，D2，…，Dn ，允许其中某些域是相同的。 2.D1，D2，…，Dn的笛卡尔积为 D1×D2×...×Dn={(d1,d2,...,dn)∣di∈Di,i=1,2,...,n}D_{1} \times D_{2} \times ... \times D_{n} = \lbrace (d_{1},d_{2},...,d_{n}) \mid d_{i} \in D_{i},i = 1,2,...,n \rbrace D1​×D2​×...×Dn​={(d1​,d2​,...,dn​)∣di​∈Di​,i=1,2,...,n} 性质：1)所有域的所有取值的一个组合 2)不能重复 元组（Tuple） 笛卡尔积中每一个元素（d1，d2，…，dn）叫作一个n元组（n-tuple）或简称元组 分量（Component） 笛卡尔积元素（d1，d2，…，dn）中的每一个值di叫作一个分量 基数（Cardinal number） 若Di（i＝1，2，…， ...

一、词法分析器 词法分析器的三种设计方式 词法分析器生成器，手写词法分析器，自动化词法分析器 词法分析器生成器 talk is cheap，show me code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647grammar SimpleExpr;@header {package simpleexpr;}prog : stat* EOF ;stat : expr ';' | ID '=' expr ';' | 'if' expr ';' ;expr : expr ('*' | '/') expr | expr ('+' | '-') expr | '(' expr ')' ...