Грамматика - непосредственный составляющий
Cтраница 1
Грамматика непосредственных составляющих ( НС-грамматика) выражает свои правила в терминах компонентов языка и указывает на то, как они могут соединяться между собой. [1]
Грамматики непосредственных составляющих все еще носят более общий характер, чем это необходимо или желательно. В частности, Р должна быть конечной для вычислений, требующихся при построении трансляторов. Более того, эти грамматики допускают цикличные определения, что является очевидной причиной несднозначности. [2]
 |
Метасимволы БНФ. [3] |
Хотя любая грамматика непосредственных составляющих может быть записана в БНФ, нотация Бэкуса не является полным метаязыком - некоторые наборы строк ( языки) нельзя специфицировать с помощью грамматик непосредственных составляющих. Однако на практике это не препятствует конструированию языка. Свойства, которые мы хотели бы сообщить языку, часто носят структурный ( грамматический) характер, а так как класв языков непосредственных составляющих ( языков, определенных о помощью грамматик непосредственных составляющих) велик, у нав имеется достаточная свобода выбора одного из них. [4]
Поскольку нетерминальные символы не входят в предложение, грамматики непосредственных составляющих, которые допускают вывод пустой строки, трудны для автоматизированных систем распознавания. Поэтому расширение алгор / тма распознавания за счет включения пустых правых частей всегда ценно и полезно. [5]
 |
Метасимволы БНФ. [6] |
Бэкуса - Наура ( БНФ), формальным метаязыком для определения грамматик непосредственных составляющих. Мы широко пользуемся этим метаязыком в настоящей книге. БНФ завоевала популярность после того, как была использована для описания синтаксиса Алгола-60 1371, но ее применение не ограничивается каким-либо конкретным языком. [7]
 |
Метасимволы БНФ. [8] |
Хотя любая грамматика непосредственных составляющих может быть записана в БНФ, нотация Бэкуса не является полным метаязыком - некоторые наборы строк ( языки) нельзя специфицировать с помощью грамматик непосредственных составляющих. Однако на практике это не препятствует конструированию языка. Свойства, которые мы хотели бы сообщить языку, часто носят структурный ( грамматический) характер, а так как класв языков непосредственных составляющих ( языков, определенных о помощью грамматик непосредственных составляющих) велик, у нав имеется достаточная свобода выбора одного из них. [9]
Заметим также, что по определению V f ] V ( пустое. Грамматика непосредственных составляющих 1 ( ГНС) является четверкой ( V, V, G, -), в которой ( V U V4, -) будет КНСПНС, Vn - множеством нетерминальных символов и Vj - множеством терминальных символов; G, некий конкретный элемент Vn, называемый начальным символом, представляет собой имя непосредственной составляющей, которая описывает весь язык целиком. [10]
Грамматика будет неоднозначной, если какое-либо предложение неоднозначно относительно нее. Неоднозначность становится проблемой, когда мы пользуемся грамматикой непосредственных составляющих для описания структуры языка. В английском языке имеется много. [11]
В настоящей главе будет затронута тема грамматического разбора, а также исследована возможность приложения Пролога к задаче написания синтаксических анализаторов. Целесообразность применения Пролога к этой задаче связана с двумя следующими соображениями. Во-первых, на Прологе легко и естественно выражаются так называемые грамматики непосредственных составляющих ( НС-грамматики), представляющие весьма важный класс грамматик для описания естественных языков. Именно такое использование Пролога провозглашалось первоначальной целью его создания. Во-вторых, в силу того, что нотация для НС-грамматик в Прологе отличается от синтаксиса фактов и правил, совершенное владение языком должно включать в себя понимание взаимосвязи между этой нотацией и стандартным синтаксисом. [12]
 |
Метасимволы БНФ. [13] |
Хотя любая грамматика непосредственных составляющих может быть записана в БНФ, нотация Бэкуса не является полным метаязыком - некоторые наборы строк ( языки) нельзя специфицировать с помощью грамматик непосредственных составляющих. Однако на практике это не препятствует конструированию языка. Свойства, которые мы хотели бы сообщить языку, часто носят структурный ( грамматический) характер, а так как класв языков непосредственных составляющих ( языков, определенных о помощью грамматик непосредственных составляющих) велик, у нав имеется достаточная свобода выбора одного из них. [14]
В общем, если А - фЛгр, то можно сказать, что грамматика рекурсивна в А. Если А - Аф, то она леворекурсивна, а если А - - фЛ, то она право рекурсивна. Почти все представляющие интерес языки бесконечны ( по крайней мере теоретически), а нам нужно, чтобы наши грамматики были конечными. Поэтому рекурсия представляет собой довольно общее свойство грамматик непосредственных составляющих. [15]
Страницы: 1