1
FIRST(X): 可以从X推导出的所有串首终结符构成的集合
如果X⇒∗εX \Rightarrow {}^* \varepsilonX⇒∗ε.那么 ε∈FIRST(X)\varepsilon \in FIRST(X) ε∈FIRST(X)
例
1◯ E→TE′FIRST(E)={(,id}2◯ E′→+TE′∣εFIRST(E′)={+,ε}3◯ T→FT′FIRST(T)={(,id}4◯ T′→∗FT′∣εFIRST(T′)={∗,ε}5◯ F→(E)∣idFIRST(F)={(,id}\begin{align*} \textcircled{1} &\ E \to TE' & \text{FIRST}(E) &= \lbrace (, \text{id} \rbrace \\ \textcircled{2} &\ E' \to +TE' \mid \varepsilon & \text{FIRST}(E') &= \lbrace +, \varepsilon \rbrace \\ \textcircled{3} &\ T \to FT' & \text{FIRST}(T) &= \lbrace (, \text{id} \rbrace \\ \textcircled{4} &\ T' \to *FT' \mid \varepsilon & \text{FIRST}(T') &= \lbrace *, \varepsilon \rbrace \\ \textcircled{5} &\ F \to (E) \mid \text{id} & \text{FIRST}(F) &= \lbrace (, \text{id} \rbrace \end{align*} 1◯2◯3◯4◯5◯ E→TE′ E′→+TE′∣ε T→FT′ T′→∗FT′∣ε F→(E)∣idFIRST(E)FIRST(E′)FIRST(T)FIRST(T′)FIRST(F)={(,id}={+,ε}={(,id}={∗,ε}={(,id}
S_文法(简单的确定性文法)
每个产生式的右部都以终结符开始
同一非终结符的各个候选式的首终结符都不同
S_文法不含ε\varepsilonε产生式
文法转换
文法GS→aAd∣aBeA→cB→b输入abc 文法G\\ S \rarr aAd | aBe \\ A \rarr c \\ B \rarr b \\ 输入 a b c 文法GS→aAd∣aBeA→cB→b输入abc
不知道写点什么,所以记一下,以防失忆
本文内容含AI生成内容
确定有限自动机(Deterministic Finite Automaton,DFA)是一种计算模型,常用于模式匹配、词法分析等领域。
一个 DFA 可以用一个五元组 (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F)(Q,Σ,δ,q0,F) 来表示,其中: