Изменения

Пусть <tex>\Gamma=\langle \Sigma, N, S, P \rangle</tex> {{---}} LL(1)-грамматика. Построим для нее парсер.

Для каждого нетерминала <tex>A</tex> : <tex>A \rightarrow \alpha_1 \mid \alpha_2 \mid ... \ldots \mid \alpha_k </tex> создадим функцию <tex> \mathtt{A}() : \mathtt{Node} </tex>, возвращающую фрагмент дерева разбора, выведенный из нетерминала <tex>A</tex>.

Здесь <tex>\mathtt{Node }</tex> {{---}} структура следующего вида: '''struct''' Node children : '''list<Node>''' value : '''string ''' <font color="green">// имя нетерминала или текст терминала</font> '''function''' addChild('''Node''') <font color="green">// функция, подвешивающая поддерево к данному узлу</font>

Токен В псевдокоде используются следующие обозначения:* <tex>\mathtt{curToken}</tex> {{---}} текущий токен строки,* <tex>\mathtt{nextToken()}</tex> {{---}} один или несколько нетерминаловфункция, для удобства объединяемые по смыслу записывающая в одну логическую единицу<tex>\mathtt{curToken}</tex> следующий за ним токен.

nextToken() {{---}} записывает в curToken следующий за ним токен.   A() : '''Node''' Node res = Node("A") '''switch ''' (curToken) :<font color="green">// принимаем решение в зависимости от текущего токена строки</font> '''case ''' <tex>\mathrm{FIRST}(\alpha_1) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha_1)) ? FOLLOW(A) : \varnothing)</tex> : <font color="green">// <tex>\alpha_1 = x_1x_2..x_X_1X_2 \ldots X_{t_1t}</tex> </font> '''for <tex>x_1 ''' i = 1 .. x_{t_1}</tex>t '''if ''' <tex>x_1X_i </tex> is terminal{{---}} нетерминал consume(<tex>x_1X_i</tex>) res.addChild(new Node("<tex>x_1X_i</tex>") nextToken() '''else''' <font color="green">// <tex>X_i</tex> {{---}} терминал, нужно вызвать </font> Node t = <tex>X_1X_i()</tex> res.addChild(t) '''break''' '''case ''' <tex>\mathrm{FIRST}(\alpha_2) \cup (\mathrm{FOLLOW}(A)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha_2)) ? FOLLOW(A) : \varnothing)</tex> :

'''break'''

'''default ''' : <font color="red">error</font>("unexpected char") '''return ''' res

'''function''' consume(c: '''char c''') '''if (''' curToken != c) <font color="red">error</font>("expected" + c)