A feladat:

Adott az alábbi nyelvtan mely logikai kifejezéseket generál.

\begin{eqnarray*} A& \ensuremath{\rightarrow}& A\vee B\;\vert\;B\\ B&\ensuremat... ...rightarrow}&p(X)\;\vert\;(A) \\ X & \ensuremath{\rightarrow}&x \end{eqnarray*}



a) Készítsen operátor precedencia elemzőt a nyelvtanhoz!
b) Elemezze segítségével az $p(x)\wedge\neg p(x)$ mondatot!

A megoldás:

  $\vee$ $\wedge$ $\neg$ $\forall$ ( ) p x $\epsilon$
$\vee$ \ensuremath{\cdot>} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{\cdot>} \ensuremath{<\cdot}   \ensuremath{\cdot>}
$\wedge$ \ensuremath{\cdot>} \ensuremath{\cdot>} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{\cdot>} \ensuremath{<\cdot}   \ensuremath{\cdot>}
$\neg$ \ensuremath{\cdot>} \ensuremath{\cdot>}   \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{\cdot>} \ensuremath{<\cdot}   \ensuremath{\cdot>}
$\forall$         \ensuremath{\dot{=}}     \ensuremath{<\cdot}  
( \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{\dot{=}} \ensuremath{<\cdot} \ensuremath{<\cdot}  
) \ensuremath{\cdot>} \ensuremath{\cdot>}       \ensuremath{\cdot>}     \ensuremath{\cdot>}
p         \ensuremath{\dot{=}}        
x         \ensuremath{\cdot>} \ensuremath{\cdot>}      
$\epsilon$ \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot} \ensuremath{<\cdot}   \ensuremath{<\cdot}    




Az egyszerűsített nyelvtan (ami úgy jön, hogy mindenkit $A$-nak hívunk):
$A\ensuremath{\rightarrow}A\vee A, 1$,
$A\ensuremath{\rightarrow}A\wedge A, 2$,
$A\ensuremath{\rightarrow}\neg A, 3$
$A\ensuremath{\rightarrow}\forall A(A), 4$,
$A\ensuremath{\rightarrow}p(A), 5$,
$A\ensuremath{\rightarrow}(A), 6$
$A\ensuremath{\rightarrow}x, 7$

Az elemzés:

Elöl áll a veremtartalom, középen az input, hátul a kimenet.:



$\epsilon\;\;\;\;\;\;\;\;p(x)\wedge \neg p(x)\;\;\;\;\;\;\;\;\epsilon\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}p\;\;\;\;\;\;\;\;(x)\wedge \neg p(x)\;\;\;\;\;\;\;\;\epsilon\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}p\ensuremath{\dot{=}}(\;\;\;\;\;\;\;\;x)\wedge \neg p(x)\;\;\;\;\;\;\;\;\epsilon\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}p\ensuremath{\dot{=}}(\ensuremath{<\cdot}x\;\;\;\;\;\;\;\;)\wedge \neg p(x)\;\;\;\;\;\;\;\;\epsilon\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}p\ensuremath{\dot{=}}( A\;\;\;\;\;\;\;\;)\wedge \neg p(x)\;\;\;\;\;\;\;\;7\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}p\ensuremath{\dot{=}}( A\ensuremath{\dot{=}})\;\;\;\;\;\;\;\;\wedge \neg p(x)\;\;\;\;\;\;\;\;7\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$A\;\;\;\;\;\;\;\;\wedge \neg p(x)\;\;\;\;\;\;\;\;75\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge \;\;\;\;\;\;\;\;\neg p(x)\;\;\;\;\;\;\;\;75\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge \ensuremath{<\cdot}\neg\;\;\;\;\;\;\;\;p(x)\;\;\;\;\;\;\;\;75\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge \ensuremath{<\cdot}\neg\ensuremath{<\cdot}p\;\;\;\;\;\;\;\;(x)\;\;\;\;\;\;\;\;75\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge \ensuremath{<\cdot}\neg\ensuremath{<\cdot}p\ensurema... ...}}(\;\;\;\;\;\;\;\;x)\;\;\;\;\;\;\;\;75\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge \ensuremath{<\cdot}\neg\ensuremath{<\cdot}p\ensurema... ...ot}x\;\;\;\;\;\;\;\;)\;\;\;\;\;\;\;\;75\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge \ensuremath{<\cdot}\neg\ensuremath{<\cdot}p\ensurema... ...}(A\;\;\;\;\;\;\;\;)\;\;\;\;\;\;\;\;757\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge \ensuremath{<\cdot}\neg\ensuremath{<\cdot}p\ensurema... ...;\;\;\;\;\;\epsilon \;\;\;\;\;\;\;\;757\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge \ensuremath{<\cdot}\neg A\;\;\;\;\;\;\;\;\epsilon \;\;\;\;\;\;\;\;7575\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$\ensuremath{<\cdot}A\wedge A\;\;\;\;\;\;\;\;\epsilon \;\;\;\;\;\;\;\;75753\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
$A\wedge A\;\;\;\;\;\;\;\;\epsilon \;\;\;\;\;\;\;\;757532\;\;\;\;\;\;\;\;\ensuremath{\rightarrow}$
Accept (757532).