177
правок
Изменения
→Псевдокод
f = createState
<tex>F \leftarrow \{f\} </tex>
'''return''' makeFA (s,S,f)
'''function''' makeFA (q0,a,q1):
'''if''' a == <tex> \varepsilon </tex> || a <tex> \in \Sigma</tex> <font color=green>// пришли в лист дерева разбора</font>
<tex> \Delta = \Delta \cup \{(q_0,a,q_1)\} </tex>
'''if''' a == <tex>X\beta</tex> '''where''' <tex> X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| > 0 </tex>
q = createState
makeFA (<tex>q_0,X,q_1</tex>) makeFA (<tex>q, \beta, q_1 </tex>)
'''return'''
'''if''' '''exist''' <tex> N_i </tex> '''where''' <tex> a \in N_i </tex>
'''if getTheTypeOfMutualRecursiveSet'''(<tex> N_i </tex>) == '''left'''
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1 \ldots X_m \land X_1, \ldots X_m \neq N_i </tex>
makeFA (<tex>q_0, X_1 \ldots X_m, q_C</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1 \ldots X_m \land X_1, \ldots X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \ldots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} </tex>
'''else''' <font color=green>// рекурсивный нетерминал right или cyclic</font>
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1 \ldots X_m \land X_1, \ldots X_m \neq N_i </tex>
makeFA (<tex>q_C, X_1 \ldots X_m, q_1</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1 \ldots X_m \land X_1, \ldots X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \ldots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\} </tex>
'''return'''
'''foreach''' p '''in''' <tex>P</tex> '''where''' p == <tex> a \rightarrow \beta </tex>
makeFA (<tex> q_0, \beta, q_1 </tex>)
== Аппроксимации самоприменимой грамматики ==
