# Precedence Table Construction Algorithm for CFGs Regardless of Being OPGs
## 3 Previous Work  
According to [1; 11; 14], for a CFG \(G\), the left terminal sets \(\mathcal{L}_{G}(A)\) and right terminal sets \(\mathcal{R}_{G}(A)\) are defined as follows:  
\[\mathcal{L}_{G}(A)=\Big{\{}a|A\xrightarrow{*}\gamma a\alpha,\gamma\in N\cup \{\epsilon\}\Big{\}}.\]  
\[\mathcal{R}_{G}(A)=\Big{\{}a|A\xrightarrow{*}aa\gamma,\gamma\in N\cup\{ \epsilon\}\Big{\}}.\]  
Precedence relationships arise from the parse tree's establishment of binary relationships between consecutive terminals or those that become sequential after a bottom-up process toward the non-terminal symbol \(S\).  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Stack** & **Input** & **Action** \\ \hline \(\$\) & \(w\$\) & \\ \hline \(\cdots\) & \(\cdots\) & Shift/Reduce \\ \hline \(\cdots\) & \(\cdots\) & Shift/Reduce \\ \hline \(\$\$\) & \(\$\) & _Accept_ \\ \hline \hline \end{tabular}
\end{table}
Table 1: Bottom-up parsing table.  
The precedence relationships are established as follows:  
1. \(a\doteq b\), if and only if \(\exists A\longrightarrow\alpha a\gamma b\beta\in P,\gamma\in N\cup\{\varepsilon\}\).
2. \(a\preccurlyeq b\), if and only if \(\exists A\longrightarrow\alpha aD\beta\in P,b\in\mathcal{L}_{G}(D)\).
3. \(a\gtrdot b\), if and only if \(\exists A\longrightarrow\alpha Db\beta\in P,a\in\mathcal{R}_{G}(D)\).  
According to [2], precedence relations are used to delimit a handle in a right-sentential form. That is, in the sentential form \(\alpha\beta w\), the substring \(\beta\) is a handle if there is a production \(A\longrightarrow\beta\) in the CFG; therefore, it can be delimited by the precedence relations, obtaining \(\alpha\preccurlyeq\beta\gtrdot w\). The relation \(\doteq\) between the symbols used when the handle has more than one consecutive terminal symbol. That is, if \(\beta=a_{1}a_{2}\ldots a_{n}\), then the relation \(a_{i}\doteq a_{i+1},\forall i=1,\ldots,n-1\) should be established. Suppose a right-sentential form is \(A_{0}a_{1}A_{1}a_{2}\ldots a_{n}A_{n}\), where each \(A_{i}\) is a non-terminal. In that case, the relations can be established as \(a_{i}\lessdot A_{i}a_{i+1}\), with a maximum of one non-terminal (operator grammar principle) between the terminals. Non-terminals could be eliminated in the right sentential form, leaving only the relationships between terminals.  
In short, each time a handle is obtained, it can be enclosed between the symbols of \(\lessdot\) and \(\gtrdot\). In addition, two consecutive terminal symbols can be inside a handle (non-terminals in the middle), and the relationship is to be established \(\doteq\). Finally, non-terminal symbols can be removed from the right-sentential form when a handle is found and locked between the precedence relations.  
According to [2], the concepts discussed in Section 2.8, and the precedence relations, the precedence parsing Algorithm 1 is constructed as follows:  
```
0: Set of precedence relations. procedurePereedenceParsing(\(w\)) \(stack\leftarrow[\$]\) \(end\gets false\) \(pos\gets 0\)do \(a\gets stack[top]\) \(b\gets tw\$[pos]\) if\(a=\$\)and\(b=\$\)then  print(\"Action: Accept\")  end\(\leftarrow\)\(true\) else if\(a\lessdot b\)or\(a\doteq b\)then \(pos++\)  push(\(stack,b\))  print(\"Action: Shift\") else if\(a\gtrdot b\)then  do \(e\leftarrow\)\(\texttt{pull}(stack)\) whilenot\((stack[top]\lessdot e)\)  print(\"Action: Reduce\") else  print(\"Action: Error\")  end\(\leftarrow\)\(true\) endif endif endif whilenot\(end\) endprocedure
```  
**Algorithm 1** Precedence parsing algorithm