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



1. Nyél belseje


$a\ensuremath{\dot{=}} b$, ahol $a,b\in \Sigma$,


ha


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


2. Nyél eleje


(a)
$\epsilon \ensuremath{<\cdot} b$ , ahol $b\in \Sigma$ ,


ha


$S{\ensuremath{\rightarrow} }^+ b\gamma$ vagy $S{\ensuremath{\rightarrow} }^+ Xb\gamma$ ( $\gamma\in \ensuremath{{(N\cup \Sigma)}^*} , X\in N$ )


azaz, ha S -ből $\geq 1$ lépésben levezethető egy olyan mondatszerű forma, amelynek elején (modulo egy darab nemterminális) b áll.


(b)
$a\ensuremath{<\cdot} b$ , ahol $a,b\in \Sigma$ ,


ha


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


azaz, ha valamelyik szabályban a után olyan B nemterminális áll, amiből $\geq 1$ lépésben levezethető egy olyan mondatszerű forma, amelynek elején (max egy nemterminális után esetleg) b áll.


3. Nyél vége


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


ha


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


azaz, ha S -ből $\geq 1$ lépésben levezethető egy olyan mondatszerű forma, amelynek végén (esetleg egy darab nemterminális előtt) a áll.


(b)
$a\ensuremath{\cdot>} b$ , ahol $a,b\in \Sigma$ ,


ha


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


azaz, ha valamelyik szabályban olyan B nemterminális után áll a b , amiből $\geq 1$ lépésben levezethető egy olyan mondatszerű forma, amelynek végén a áll (esetleg van még utána egy nemterminális).