# Building Greibach Normal Form Grammars Using Genetic Algorithms
## 3 Proposed Algorithm of Grammatical Evolution for Greibach Context-Free Grammars
### CFG and GNF Parsing Algorithms  
In order to estimate the GE fitness of each chromosome GNF, a parsing algorithm must be implemented. Optimal parsing algorithms do exist for CFGs that solve the problem of whether a string can be generated by a CFG. Most of the parsers solve the problem of parsing in polynomial time O(\(n^{2}\)) up to O(\(n^{4}\)), \(n\) being the length of the candidate string to be parsed. The computational complexity of the parsing algorithm depends on the implementation of the parser and the form of the CFG. Notable parsers are the CYK algorithm [22], Early algorithm [23] and GLR [24]. The CFG parsers can be divided in two main categories :  
1. top-down parsers [25] which search the candidate string from left to right and usually implement a structure like a search tree;
2. bottom-up parsers [26] which search the candidate string from right to left and are usually implemented through dynamic programming techniques. Top-down parsers fail when left-recursions occur [27] (\(A\to AB\)) and bottom-up parsers fail when right-recursions occur (\(A\to BA\)) in some production rules. For general CFGs, hybrid implementations of top-down and bottom-up parsers are used. Greibach Normal Form offers two interesting properties which accelerate the parsing process. GNF is a left-recursion free grammar which means that any top-down parser will halt at maximum depth \(n\). Left-recursion-free means that one non-terminal symbol cannot exist both in the head of a production rule and also be the leftmost symbol in the body of a production rule. Additionally, every production rule consists of a terminal symbol which means that, at most, \(n\) production rules are used in a successful parsing path in the parsing tree. In our implementation we used a top-down parser which also provides an easy way to measure the sub-parsed string as a tree is generated. Hybrid parsers for general CFGs are worst-case scenario O(\(n^{3}\)) but bottom-up parsers have lower order in respect to the candidate string compared to the general case. The parser used in our implementation is O(\(n^{2}\log n\)) which furthermore accelerates the whole process. The proposed parsing method was carried out in two steps used recurrently. First, the components of the method were analyzed and the pseudocode of the method will be presented after this. The special notation used for the pseudocode is the sets \((S,N,T,P)\) of a 4-tuple GNF \(G\) represented as \((G.S,G.N,G.T,G.P)\) respectively and \(w\) is the candidate word to be parsed and consists only of symbols in set T. The notation \(w_{n}^{m}\) means the sub-string from index \(n\) to index \(m\) (\(m>n\) and \(m<\) length of \(w\)). Additionally, the notations \(rule_{NTerminals},rule_{Terminal}\) and \(rule_{Head}\) represent the body of the rule, without the terminal symbol in the GNF, the terminal symbol of a GNF production rule and the head of a production rule, respectively. Each component of the algorithm returns a 2-tuple Parsed,Depth whereas Parsed is a Boolean and Depth is an integer. The two steps are called ParseWord and Distribute. { Parsed,Depth } = ParseWord(StartSymbol,\(G\),\(w\))  
Minimum Depth = length of w  
for **rule** in \(G\).\(P\)  
if \(\textbf{rule}_{Terminal}\ ==w[0]\) & \(\textbf{rule}_{Head}\ ==\) StartSymbol  
case 1 : { _rule length = 2 & word length = 1 }_  
return { true,0 }  
case 2 : { _rule length = 3 & word length > 1 }_  
Minimum Depth- = 1  
check ParseWord{ \(\textbf{rule}_{NTerminals}\), G, \(w_{1}^{end}\)}  
case 3 : { _rule length > 3 & word length > 2 }_  
Minimum Depth = 1  
check Distribute[ \(\textbf{rule}_{NTerminals}\), G, \(w_{1}^{end}\)]  
end for  
return { False, Minimum Depth }  
end ParseWord  
In the above function, with the instruction check, it is meant that if the recurrent call of the function returns true, then the for loop is terminated and the 2-tuple of the called function is returned by the ParseWord{... } function.