# Precedence Table Construction Algorithm for CFGs Regardless of Being OPGs
## 1 Introduction  
This paper delves into the operator precedence languages family (OPL), created by [PERSON] [1], which is used for efficient bottom-up parsing [2; 3]. The author's inspiration from the structure of arithmetic expressions, where precedence is assigned to multiplicative operators (\(*\) and \(/\)) over additive operators (\(+\) and \(-\)), is a key insight. Through the process of bottom-up parsing, the left side (non-terminal symbol) completely replaces the identified right-side production (body) in a context-free grammar (CFG), leaving no room for ambiguity. Operator precedence was extended to grammars that consist of terminals on the right side, even if non-terminals separated them. A CFG is generally considered an operator precedence grammar (OPG) if it does not contain productions with adjacent non-terminal symbols on its right-hand side. OPLs have greatly aided in inferring context-free grammars. An example is described in [4; 5; 6], where a method is presented for inferring operator precedence-free grammars from bracketed samples. The method is based on constructing parse trees and utilizing functions that produce the grammars. Precedence rules are used to identify the brackets surrounding the terminal elements of a string in the sample, indicating the order in which the string should be evaluated. Research on input-driven formal languages (IDL) [7; 8; 9] (later renamed as Visibly Pushdown Languages (VPL) [10]) has concluded [11] that OP closure properties imply ID closure properties and that ID languages are a specific type of OP languages characterized by limited OP relations [12]. Since the advancements in parallel computing, local parsability properties derived from OPL have been utilized to generate fast parallel parsers [13]. This paper's main contribution is its novel approach to building precedence relationships between terminal symbols in non-OPGs. This approach allows the generation of operator precedence tables and bottom-up parsing on a string derived by the non-OPG with support from the table obtained. The novelty of the work is a significant aspect that sets it apart from previous research in the field. * The sets of Left and Right terminals proposed in previous works [1; 11; 14] to build precedence relationships between the terminals of an OPG were redefined. * A new set of terminals called Leftmost was defined to support solving precedence relationships when there are two or more adjacent terminals on the right side of the productions. This set is significant as it systematically handles the precedence relationships in such complex scenarios, expanding the bottom-up parsing process with non-OPGs. * An algorithm was established to build the precedence table with the support of the three sets of terminals proposed. * Finally, applying the proposed algorithms makes it possible to obtain from a non-OPG the relations and operator precedence table previously limited to OPGs only. In addition, a bottom-up operator-precedence parser could be used to parse any string generated by a non-OPG, a technique that could only be applied to OPGs. As demonstrated in this work, the proposed solution to construct the operator precedence table is not just a theoretical concept but a practical tool that can be applied to OPGs without any restrictions. At the end of the work, the functionality is demonstrated by applying it to an OPG and two non-OPGs and carrying out the respective bottom-up parsing. This practical demonstration should instill confidence in the effectiveness of the proposed solution and ensure its practical applicability. The paper is organized as follows: Section 2 provides the necessary definitions to understand this work. Section 3 presents the previous work carried out in the area of CFG. Section 4 introduces our approach, detailing the problem we aim to solve and the redefinitions of previous works' concepts used to develop our algorithms.