# Precedence Table Construction Algorithm for CFGs Regardless of Being OPGs
## 4 Approach
### Problem Analysis
#### 4.2.2 General Grammar with Two or More Consecutive Non-Terminal Symbols  
Redefinition of Left, Right and definition of Leftmost. **Left(\(B\)):**  
Given the rightmost derivation:  
\[\gamma_{1}aBx_{1}\Longrightarrow\gamma_{1}a\omega_{1}x_{1}. \tag{3}\]  
It is observed that \(\omega_{1}\) is a handle within a bottom-up parsing (inverse rightmost derivation) since \(B\Longrightarrow\omega_{1}\); therefore, from (3), it can be established that \(\gamma_{1}a\lessdot\omega_{1}\gtrdot x_{1}\). In addition, \(\omega_{1}\) can have the following forms:  
(a) \(\omega_{1}=\beta_{1}b\gamma_{2}\). (b) \(\omega_{1}=\beta_{1}C\gamma_{3}\). Continuing with the rightmost derivation in (3) and taking each of the options of \(\omega_{1}\), we obtain that:  
(a) \(\gamma_{1}aBx_{1}\Longrightarrow\gamma_{1}a\beta_{1}b\gamma_{2}x_{1}\) since \(\omega_{1}\) is a handle, consequently \(\gamma_{1}a\lessdot\beta_{1}b\gamma_{2}\gtrdot x_{1}\); therefore, \(a\lessdot b\) where \(B\longrightarrow\beta_{1}b\gamma_{2}\) and \(b\in\mathcal{L}(B)\). (b) \(\gamma_{1}aBx_{1}\Longrightarrow\gamma_{1}a\beta_{1}C\gamma_{3}x_{1} \stackrel{{*}}{{\Longrightarrow}}\gamma_{1}a\beta_{1}Cx_{2}x_{1} \stackrel{{*}}{{\Longrightarrow}}\gamma_{1}a\beta_{1}\beta_{2}Dx_{ 3}x_{2}x_{1}\Longrightarrow\gamma_{1}a\beta_{1}\beta_{2}\beta_{3}b\gamma_{4}\)\(x_{3}x_{2}x_{1}\). It is observed that \(C\Longrightarrow\beta_{2}Dx_{3}\) and \(D\longrightarrow\beta_{3}b\gamma_{4}\); therefore, \(\beta_{3}b\gamma_{4}\) is a handle, and consequently \(\gamma_{1}a\beta_{1}\beta_{2}\lessdot\beta_{3}b\gamma_{4}\gtrdot x_{3}x_{2}x_{1}\) and \(a\lessdot b\). In short, \(\gamma_{1}aBx_{1}\stackrel{{*}}{{\Longrightarrow}}\gamma_{1}a \beta_{1}\beta_{2}\beta_{3}b\gamma_{4}x_{3}x_{2}x_{1}\); taking \(\beta=\beta_{1}\beta_{2}\beta_{3}\) and \(\gamma_{5}=\gamma_{4}x_{3}x_{2}\), we obtain the summary derivation \(\gamma_{1}aBx_{1}\stackrel{{*}}{{\Longrightarrow}}\gamma_{1}a \beta b\gamma_{5}x_{1}\), where \(B\stackrel{{*}}{{\Longrightarrow}}\beta b\gamma_{5}\) and \(b\in\mathcal{L}(B)\). **Right(\(B\)):**  
Given the rightmost derivation:  
\[\gamma_{1}Bax_{1}\Longrightarrow\gamma_{1}\omega_{1}ax_{1}. \tag{4}\]  
It is observed that \(\omega_{1}\) is a handle within a bottom-up parsing (inverse rightmost derivation), since \(B\Longrightarrow\omega_{1}\); therefore, from (4), it can be established that \(\gamma_{1}\lessdot\omega_{1}\gtrdot ax_{1}\). In addition, \(\omega_{1}\) can have the following forms:  
(a) \(\omega_{1}=\gamma_{2}b\beta\). (b) \(\omega_{1}=\gamma_{3}C\beta_{1},\beta_{1}\stackrel{{*}}{{ \Longrightarrow}}\varepsilon\). Continuing with the rightmost derivation in (4) and taking each of the options of \(\omega_{1}\), we obtain that:  
(a) \(\gamma_{1}Bax_{1}\Longrightarrow\gamma_{1}\gamma_{2}b\beta ax_{1}\) since \(\omega_{1}\) is a handle, consequently \(\gamma_{1}\lessdot\gamma_{2}b\beta\gtrdot ax_{1}\); therefore, \(b\gtrdot a\) where \(B\longrightarrow\gamma_{2}b\beta\) and \(b\in\mathcal{R}(B)\). (b) \(\gamma_{1}Bax_{1}\Longrightarrow\gamma_{1}\gamma_{3}C\beta_{1}ax_{1} \stackrel{{*}}{{\Longrightarrow}}\gamma_{1}\gamma_{3}\gamma_{4}Dax_{1} \Longrightarrow\gamma_{1}\gamma_{3}\gamma_{4}\gamma_{5}b\beta_{2}ax_{1}\). It is noted that \(C\stackrel{{*}}{{\Longrightarrow}}\gamma_{4}D\) and \(D\longrightarrow\gamma_{5}b\beta_{2}\); therefore, \(\gamma_{5}b\beta_{2}\) is a handle, and consequently,\[\gamma_{1}\gamma_{3}\gamma_{4}\leq\gamma_{5}b\beta_{2}>ax_{1}\text{ and }b>a.\]  
In short, \(\gamma_{1}Bax_{1}\overset{+}{\implies}\gamma_{1}\gamma_{3}\gamma_{4}\gamma_{5}b \beta_{2}ax_{1}\); taking \(\gamma_{6}=\gamma_{3}\gamma_{4}\gamma_{5}\), we obtain the summary derivation \(\gamma_{1}Bax_{1}\overset{+}{\implies}\gamma_{1}\gamma_{6}b\beta_{2}ax_{1}\), where \(B\overset{+}{\implies}\gamma_{6}b\beta_{2}\) and \(b\in\mathcal{R}(B)\). **Leftmost(\(B\)):**  
Given the production with two non-terminal symbols on the right (body):  
\[S\longrightarrow AB \tag{5}\]  
\[A\longrightarrow\gamma_{1}b_{1}\beta_{1} \tag{6}\]  
Rightmost derivation from \(S\) in (5) is:  
\[