Search

0.6.2 Cheatham Sattley Method

Cheatham Sattley is an easy to implement, tabular method of language parsing. It is a top-down system, like recursive descent, but it is a predictive system where, based on alternatives in syntax, the parser attempts to guess at what language element will come next.

Cheatham Sattley is good at parsing languages whose syntax can be stated in the following format:

<lhs> ::= <e₁₁><e₁₂> | <e₂₁><e₂₂>

Of course some elements can be terminals or empty elements.

When told to match a <lhs>, Cheatham Sattley will initially predict that the first token presented should be a e₁₁. If this prediction fails, it will next try to parse the same initial token as a e₂₁. This process can continue n times until either the token is matched or no matches occur. In essence, Cheatham Sattley is a tree walking algorithm.

$$\begin{eqnarray*}{c} S \Longrightarrow BA \vert C \\ B \Longrightarrow ab \\ A \Longrightarrow a \\ C \Longrightarrow c \\ \end{eqnarray*}$$