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

асфальт стоимость, дорожный ремонт, технология укладки асфальта | Узел обвязки.

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


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

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

         

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

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

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


  •  




    - Начало -  - Назад -  - Вперед -