Синтаксические диаграммы
- Для того, чтобы улучшить зрительное восприятие и облегчить понимание сложных синтаксических описаний, применяют представление правил грамматики в виде синтаксических диаграмм. Правила построения таких диаграмм можно сформулировать в следующем виде:
1) Каждому правилу вида <A> ® a1
| a2 |...| ak ставится в соответствие диаграмма, структура которой определяется правой частью правила.
2) Каждое появление терминального символа x в цепочке ai
изображается на диаграмме дугой, помеченной этим символом x, заключенным в кружок.
3) Каждому появлению нетерминального символа <A> в цепочке ai ставится в соответствие на диаграмме дуга, помеченная символом, заключённым в квадрат.
- 4) Порождающее правило, имеющее вид:
- <A> ® a1a2...an
изображается на диаграмме следующим образом:
- 5) Порождающее правило, имеющее вид:
- <A> ® a1 | a2 | ... | an
изображается на диаграмме так:
- 6) Если порождающее правило задано в виде итерации:
- <A> ® {a}*,
то ему соответствует диаграмма:
Число синтаксических диаграмм, которые можно построить для заданной схемы грамматики, определяется числом правил. Чтобы сократить число диаграмм, их объединяют, заменяя нетерминальные символы, входящие в диаграмму, построенными для них диаграммами.
Правила 3-6 предусматривают, что в качестве цепочки a1 на объединенной диаграмме могут быть использованы диаграммы построенные для этих цепочек. В качестве примера рассмотрим следующую грамматику с начальным символом <A> :
- Г1. 14: Vт = { x, +, (, ) }, Va = {<A>, <B>, <C>},
- R = {<A> ® x | (<B>),
- <B> ® <A><C>,
<C> ® {+<A>}*}.
Синтаксические диаграммы для такой грамматики имеют вид:
Заменяя нетерминальные символы, соответствующими диаграммами, получаем объединенную диаграмму в виде:
Пред.Страница След.Страница Раздел Содержание