Формальные языки




Синтаксические диаграммы


    Для того, чтобы улучшить зрительное восприятие и облегчить понимание сложных синтаксических описаний, применяют представление правил грамматики в виде синтаксических диаграмм. Правила построения таких диаграмм можно сформулировать в следующем виде:

    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>}*}.

               

            Синтаксические диаграммы для такой грамматики имеют вид:

            Заменяя нетерминальные символы, соответствующими диаграммами, получаем объединенную диаграмму в виде:

            Пред.Страница  След.Страница   Раздел   Содержание


             




            Содержание  Назад  Вперед