## 4.5. Parsing

In formal language theory, parsing - or the so called syntactic analysis - is a process when the parser determines if a given string can be generated by a given grammar. This is very important for compilers and interpreters. For example, it is not too difficult to create a context-free grammar GP generating all syntactically correct Pascal programs. Then, we can use a parser to decide - about a Pascal program written by a programmer - if the program is in the generated language L(GP). When the program is in the generated language, it is syntactically correct.

### 4.5.1. The CYK Algorithm

We have a given Chomsky normal form grammar G = (N, T, S, P) and a word p = a1a2... an. The Cocke-Younger-Kasami algorithm is a well known method to decide wether pL(G) or pL(G). To make our decision, we have to fill out an n × n size triangular matrix M in the following way: Over the cells of the first line, we write the letters a1,a2,...,an, starting from the first letter, one after the other. Then, the cell M(i,j) contains each nonterminal symbol A, if and only if the subword ajaj+1...aj+i-1 can be derived from A. (Formally: AM(i,j) if and only if A* ajaj+1...aj+i-1.) This means that the first cell of the first line contains the nonterminal A, if and only if Aa1P. The cell M(1,j) contains the nonterminal A, if and only if AajP. It is also quite easy to fill out the cells of the second line of the matrix. The nonterminal A is in the cell M(2,j), if and only if there exists nonterminals B, CN such that BM(1,j), CM(1,j+1), and ABCP. From this point the algorithm becomes more complex. From the third line, we use the following formula: AM(i,j), if and only if there exists nonterminals B, CN and integer k such that BM(k,j), CM(i-k, j+k) and ABCP. This algorithm is finished when the cell M(n,1) is filled out. Remember, the nonterminal A is in the cell M(i,j), if and only if the word ajaj+1...aj+i-1 can be derived from A. This means that the nonterminal S is in the cell M(n,1), if and only if the word a1a2...an can be derived from S. So the grammar G generates the word p, if and only if the cell M(n,1) contains the start symbol S.

Example 45. In this example, we use the CYK algorithm to show that the grammar G generates the word abbaa.

```G = ({S, A, B}, {a,b}, S, P)
P = {
S → SA,
S → AB,
A → BS,
B → SA,
S → a,
A → a,
B → b
}```

As you can see, SM(5,1), so abbaaL(G).

Exercise 60. Use the CYK algorithm to show that the grammar G generates the word baabba.

```G = ({S, A, B, X, Y, Z}, {a,b}, S, P)
P ={
S → AY,
Y → XB,
X → BA,
X → ZA,
Z → BX,
A → b,
B → a
}```

Exercise 61. Use the CYK algorithm to decide if the word cbacab can be generated by grammar G.

```G = (S, A, B, C, D}, {a,b,c}, S, P)
P = {
S → AB,
A → CA,
A → SS,
B → CD,
A → b,
C → a,
C → b,
D → c
}```

### 4.5.2. The Earley Algorithm

The Earley algorithm is designed to decide if a context-free grammar generates a terminal word. Sometimes it is not comfortable to create and use an equivalent Chomsky normal form grammar for a λ-free context-free grammar, because the Chomsky normal form grammar could have many more production rules than the original grammar. This is why the Earley algorithm is more widely used than the CYK algorithm for computerized lexical analysis. Although the Earley algorithm looks more complicated for humans, - and actually, it is more complicated compared to the the very simple CYK algorithm, - but after the implementation, there is no difference between the complexity of the two algorithms for computers.

Now we are going to show the steps of the λ-free version of the Earley algorithm. It can work with rules having form A → λ as well, with minor modification, but in practice we do not need the extended version.

#### Earley Algorithm

Let G = (N, T, S, P) be a λ-free, context-free grammar, and p = a1a2... anT+, with integer n > 0. We are going to fill out the cells of an (n+1) × (n+1) triangular matrix M, except for the last cell M(n,n). Over the cells of the first line of the matrix, we write the letters a1, a2,..., an, starting from the second cell and first letter, one after the other. The elements of the matrix are production rules from P, where the right hand side of each rule contains a dot character.

The steps of the algorithm are the following:

1. Let S.qM(0,0) if SqP, and let j = 0.

2. Let A.qM(j,j) if AqP, and there exists an integer kj such that Br.AtM(k,j).

3. Let j = j+1 and let i = j-1.

4. Let Araj.tM(i,j) if Ar.ajtM(i,j-1).

5. Let ArB.tM(i,j) if there exists an integer ik < j such that Ar.BtM(i,k), and Bq.M(k,j).

6. If i > 0 then i = i-1 and goto 4.

If i = 0 and j < n then goto 2.

If i = 0 and j = n then finished.

Here q ∈ (TN)+, A, BN, r, t ∈ (TN)*, and of course i,j,k are integers.

Grammar G generates the word p (pL(G)), if and only if there is a production rule in M(0,n), whose left hand side is the start symbol S, and there is a dot at the end of the right hand side of the rule.

Examplee 46. In this example, we have a λ-free context-free grammar G, and we have to decide if the word a*a+a can be generated by this grammar.

```G = ({S, A, B}, {a,+,*,(,)}, S, P)
P = {
S → S+A
A → A*B
B → (S)
S → A
A → B
B → a
}```

As you can see, the top right cell contains a rule, whose left hand side is the start symbol S, and there is a dot at the end of the right hand side of the rule, so a+a*aL(G).

Exercise 62. Use the Earley algorithm to decide if the word 100110 can be generated by grammar G.

```G = ({S, A, B}, {0,1}, S, P)
P = {
S → 0A1,
S → 1B0,
A → B1,
B → S1,
A → 0,
B → 1
}```

Exercise 63. Use the Earley algorithm to decide if the word bbabb can be generated by grammar G.

```G = ({S, A, B}, {a,b}, S, P)
P = {
S → BA
B → bAB,
A → BAb,
B → SbA,
A → a,
B → b
}```