Сборник по задачам и примерам Assembler


Формальное описание языка программирования - часть 5


  • Класс 1. Контекстно-чувствительные грамматики. Правила этих грамматик имеют форму: AuB=>AwB. Замена и на v возможна лишь в контексте строк А и В (отсюда и название). При этом: ueVn; we(VnuVt)*; A, Be(VnuVt)+. Символы * и + обозначают множество всех строк, выводимых в рамках данной грамматики, включая ("*") и исключая ("+") пустую строку.
  • Класс 2. Контекстно-свободные, или контекст}ю-нечувствительные, грамматики. Их правила имеют форму: u=>w, где ueVn, we(VnuVt)*. Название данного класса грамматик отражает тот факт, что и можно заменить на w, не обращая внимания на контекст. Другая особенность грамматик этого класса в том, что в правой части всех правил грамматики стоит только один нетерминал. Отметим, что языки программирования моделируются с использованием грамматик именно этого класса.
  • Класс 3. Регулярные, или автоматные, грамматики. Исходя из вида правил, которые используются в таких грамматиках, их делят на два подкласса.
  • Грамматика, выравненная вправо. Ее правила имеют форму: u=>Aw или и=>А, где AeVt, u и weVn.
  • Грамматика, выравненная влево. Ее правила имеют форму: u=>\vA или и=>А, где AeVt, u и weVn. Это очень важный класс грамматик, который наряду с грамматикой класса 2 используется для моделирования языков программирования. Заметим, что рассмотренная выше грамматика языка целых чисел как раз и является грамматикой класса 3. Чтобы убедиться в этом, необходимо лишь немного подправить правила:
  • число: ."¦ цифра

    число: :*=0 число |1 число |2 число |3 число |4 число |5 число |б число |7 число

    |8 число |9 число иифра::=0|1|2|3|4(5|6|7|8|9

    Приведенная выше классификация языков была введена в 1959 году американским ученым-лингвистом Н. Хомским.

    Выше, при изложении основ работы с двусвязными списками, мы ввели понятие конечного автомата. Язык, который воспринимает любой конечный автомат, относится к языкам класса 3, то есть является регулярным. Покажем это, сформулировав грамматику для языка вещественных чисел. Напомним соответствующее регулярное выражение: (+| -)dd*.dd*e(+| 0dd*, где d* обозначает цифру 0-9 или пусто.




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