请遵守AGPL 3.0协议 本主题已开源于hexo-theme-wang

编译原理

Date Icon
Update Icon

编译原理:FIRST集和FOLLOW集

FIRST集

1

FIRST(X): 可以从X推导出的所有串首终结符构成的集合

如果XεX \Rightarrow {}^* \varepsilon.那么 εFIRST(X)\varepsilon \in FIRST(X)

1 ETEFIRST(E)={(,id}2 E+TEεFIRST(E)={+,ε}3 TFTFIRST(T)={(,id}4 TFTε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*}

算法

Date Icon
Update Icon

编译原理:LL(1)文法

S_文法

💡

S_文法(简单的确定性文法)

每个产生式的右部都以终结符开始

同一非终结符的各个候选式的首终结符都不同

S_文法不含ε\varepsilon产生式

Date Icon
Update Icon

编译原理:文法转换

文法转换

文法GSaAdaBeAcBb输入abc 文法G\\ S \rarr aAd | aBe \\ A \rarr c \\ B \rarr b \\ 输入 a b c


同一非终结符的多个候选式存在共同前缀,将导致回溯现象

Date Icon
Update Icon

编译原理:NFA转DFA

不知道写点什么,所以记一下,以防失忆

🤖

本文内容含AI生成内容

DFA

确定有限自动机(Deterministic Finite Automaton,DFA)是一种计算模型,常用于模式匹配、词法分析等领域。

定义

一个 DFA 可以用一个五元组 (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F) 来表示,其中:

  • QQ 是一个有限的状态集合。
  • Σ\Sigma 是一个有限的输入符号集合。
  • δ\delta 是状态转移函数,它将 Q×ΣQ \times \Sigma 映射到 QQ。也就是说,对于当前状态和输入符号,DFA 有唯一的下一个状态。
  • q0q_0 是初始状态,q0Qq_0 \in Q
  • FF 是接受状态集合,FQF \subseteq Q