Hogyan kell meghatározni a \ensuremath{<\cdot}, \ensuremath{\dot{=}}, \ensuremath{\cdot>}relációkat egyszerû precedencia elemzõ esetén?



1. Nyél belseje


$X\ensuremath{\dot{=}} Y$ , ahol $X,Y\in N\cup \Sigma$ ,


ha


$\exists A\ensuremath{\rightarrow}\alpha XY\beta$ szabály a nyelvtanban ( $\alpha,\beta\in \ensuremath{{(N\cup \Sigma)}^*} $ ).


Rajzzal:
\includegraphics{nyb.eps}


2. Nyél eleje


(a)
$\epsilon \ensuremath{<\cdot} Y$ , ahol $Y\in N\cup \Sigma$ ,


ha


$S{\ensuremath{\rightarrow} }^+ Y\gamma$ ( $\gamma\in \ensuremath{{(N\cup \Sigma)}^*} $ )


azaz, ha S -bõl $\geq 1$ lépésben levezethetõ egy olyan mondatszerû forma, amelynek elején Y áll.


Rajzzal:
\includegraphics{nye1.eps}


(b)
$X\ensuremath{<\cdot} Y$ , ahol $X,Y\in N\cup \Sigma$ ,


ha


$\exists A\ensuremath{\rightarrow}\alpha XB\beta$ szabály a nyelvtanban ( $\alpha,\beta\in \ensuremath{{(N\cup \Sigma)}^*} $ , $B\in N$ )
és
$B{\ensuremath{\rightarrow} }^+ Y\gamma$ ( $\gamma\in \ensuremath{{(N\cup \Sigma)}^*} $ )


azaz, ha valamelyik szabályban X után olyan B nemterminális áll, amibõl $\geq 1$ lépésben levezethetõ egy olyan mondatszerû forma, amelynek elején Y áll.


Rajzzal:
\includegraphics{nye2.eps}


3. Nyél vége


(a)
$X\ensuremath{\cdot>}\epsilon$, ahol $X\in N\cup \Sigma$ ,


ha


$S{\ensuremath{\rightarrow} }^+ \alpha X$ ( $\alpha\in \ensuremath{{(N\cup \Sigma)}^*} $ )


azaz, ha S -bõl $\geq 1$ lépésben levezethetõ egy olyan mondatszerû forma, amelynek végén X áll.


Rajzzal:
\includegraphics{nyv1.eps}


(b)
$X\ensuremath{\cdot>} a$ , ahol $X\in N\cup \Sigma, a\in \Sigma$ , (azaz a nyél vége reláció 2. szimbóluma mindig treminális)


ha


$\exists A\ensuremath{\rightarrow}\alpha BC\beta$ szabály a nyelvtanban ( $\alpha,\beta\in \ensuremath{{(N\cup \Sigma)}^*} $ , $B\in N$ , $C\in N\cup \Sigma$ )
és
$B{\ensuremath{\rightarrow} }^+ w_1X$ és $C{\ensuremath{\rightarrow} }^*Yw_2$ ( $w_1,w_2\in \ensuremath{{(N\cup \Sigma)}^*} $ )


azaz, ha valamelyik szabályban olyan B nemterminális után áll olyen C szimbólum, amikre a következõk állnak:
B -bõl $\geq 1$ lépésben levezethetõ egy olyan mondatszerû forma, amelynek végén X áll, C pedig vagy terminális és egyenlõ a -val, vagy pedig nemterminális és $\geq 1$ lépésben levezethetõ belõle egy olyan mondatszerû forma, amelynek elején Y áll.


Rajzzal, ha C terminális (és ekkor =a ):
\includegraphics{nyv2.eps}


Rajzzal, ha C nem terminális:
\includegraphics{nyv3.eps}