Язык программирования (ЯП) – это формальный язык, описывающий процесс решения задачи (алгоритм) для вычислительной машины. Язык программирования — это средство общения между человеком (пользова-телем) и компьютером (исполнителем).
Типы языков программирования.ЯП высокого уровня: Главная особенность – абстракция языка. Абстракции делают сложные задачи простыми. Сравнительно большие стандартные библиотеки означают, что то, что вы хотите сделать, скорее всего уже реализовано и доступно. ЯП низкого уровня: Больший контроль над памятью; вы можете сделать то, что практически невозможно в других языках. Позволит вам лучше понять, что происходит за кулисами в высокоуровневых языках и научит ценить абстракции. Чем больше программисту при создании программы нужно понимать и следить за работой программы, тем на ЯП более низкого уровня он программирует.
Нотации выражений. Смешанная нотация.Это - средства описания данных и средства описания действий.
Операции, определяемые комбинацией символов, нельзя классифицировать в тер-
минах префиксной, инфиксной и постфиксной нотации. Например, в выражении
if a > b then a else b совместно используются ключевые (служебные) слова if, then, else.
Значащими компонентами этого выражения являются условие a > b и выра жения a и b.
Если значением условия является true, то значением выражения является a, в противном случае — b. Говорят, что операция имеет смешанную нотацию, если ее значащие компоненты перемежаются со служебными словами (или символами).
Префиксная нотация выражения - префиксное выражение декодируется простым просмотром слева направо. Префиксная нотация константы или переменной — это сама константа или В такой нотации нет никакой неоднозначности и нет необходимости применять скобки для точного определения последовательности операций при вычислении выражения. переменная. Пример: Сумме x и y соответствует префиксная запись + x y.
Постфиксная нотация выраженияПостфиксная нотация выражения - Постфиксную нотацию иначе называют обратной польской записью. Постфиксные выражения могут вычисляться механически, с помощью структуры данных типа стек. Так как в постфиксной нотации операция записывается сразу за своими операндами, то при считывании символа операции ее операнды уже известны. Пример: Сумма x и y соответствует постфиксной записи x y +.
Инфиксная нотация выражения: приоритетность и ассоциативность.Инфиксная нотация выражения - легко читается человеком. В инфиксной нотации операции проставляются между их операндами. В сумме a и b операция сложения записывается между a и b. Точнее, так группируются левоассоциативные операции (+, –, ∗, /).
Приоритетность определяет порядок применения операции в выражении.
Операция высокого приоритета выбирает свои операнды перед операцией низкого
приоритета.
Ассоциативность задает порядок группировки в выражении операций с одинаковым приоритетом.
Правоассоциативная операция — подвыражения, содержащие ее множественные
вхождения, группируются справа налево.
Абстрактные синтаксические деревья. Лексический синтаксис.
Для простоты в формальные описания синтаксиса обычно
не включают описания синтаксических единиц самого нижнего уровня (атомов).
Подобные атомы группируют в обобщенные единицы — лексемы. Лексемы считают
основным инструментом лаконичной записи синтаксических правил.
Работу с лексемами, их детализацию описывает лексический синтаксис языка.
Лексический синтаксис задает соответствие между реальной программой и синтак-
сическими лексемами.
Абстрактное синтаксическое дерево (АСД) — это узел с k (k ≥ 0) деревьями-
потомками. Если k = 0, то дерево состоит из одного узла, без деревьев-потомков.
Узел без потомка называется листом. Корень дерева — это узел без родителя, то
есть узел, который не является потомком другого узла.
Контекстно-свободные грамматики.Повторим, что для точного и формального задания синтаксиса языка используют
грамматику. Контекстно-свободная грамматика точно определяет конкретный синтаксис и включает в себя:
1. Набор терминалов. Они являются атомарными символами языка.
2. Набор нетерминалов. Это ≪сборки≫, представляющие конструкции языка.
3. Набор правил подстановки, задающих компонентный состав конструкций. Каж-
дое правило подстановки имеет левую и правую части, разделяемые символом
≪может быть≫. В левой части находится нетерминал, в правой части — строка
из набора терминалов и нетерминалов.
4. Стартовый нетерминал. Он представляет главную конструкцию языка.
Метаязык - язык для описания другого языка.
Терминалы и нетерминалы. Нетерминалы заключаются в угловые скобки < и >, пустая строка записывается в виде <empty>. Терминалы могут заключаться в кавычки.
Правила подстановки. Метасимвол ::= означает ≪может быть≫, метасимвол | означает ≪или≫. Метасимволы | отделяют друг от друга альтернативы правых
частей (правил подстановки). Каждая альтернатива, отделяемая символом |, соответствует самостоятельному правилу.
Деревья разбора.Дерево разбора иллюстрирует процесс построения строки, имеет следующие
характеристики:
1. Каждый лист помечается терминалом или <empty>.
2. Каждый неконечный узел помечается нетерминалом.
3. Дерево разбора любого числа для этой грамматики начинается с корня к которому добавляются три потомка. Это соответствует применению первого правила подстановки.
4. Корень помечается стартовым нетерминалом.
Синтаксическая неоднозначность.Грамматика языка программирования является синтаксически неоднозначной,
если некоторая строка в его языке имеет более одного дерева разбора. Языки про-
граммирования могут описываться неоднозначными грамматиками. Если неодно-
значности существуют, вводятся соглашения, приводящие к одному дереву разбора
для каждой строки.
Выводы.Вывод состоит из последовательности строк, начинающихся со стартового не-
терминала. Каждая строка получается замещением нетерминала правой частью
одного из его правил подстановки. Вывод заканчивается, когда получают строку,
целиком состоящую из терминалов.
Пример вывода для числа 21.89
<вещ_число> -> <цел_часть> . <дробн_часть>
-> <цел_часть> <цифра> .<дробн_часть>
-> <цифра> <цифра> . <дробн_часть>
-> 2 <цифра> . <дробн_часть>
-> 21 . <дробн_часть>
-> 21 . <цифра> <дробн_часть>
-> 21 . 8 <дробн_часть>
-> 21 . 8 <цифра>
-> 21 . 89
Наиболее популярен левосторонний вывод — в нем каждый раз замещается
самый левый нетерминал.
Списки в инфиксных выраженияхПри написании правил подстановки для конструирования выражений очень важно
обеспечить рост длины выражения, управление ростом, завершение роста.
Для решения этих вопросов удобно использовать понятие списка. Выражение
a + b + c можно рассматривать как список элементов, отделяемых (или склеивае-
мых) символом +, элементы списка называются термами. Термы обычно атомарны,
но могут и иметь внутреннюю структуру.
<E> ::= <E> + <T><E> – <T><T>
<T> ::= <T> ∗ <F><T> / <F><F>
<F> ::= numbername(<E>)
Переход от абстрактного синтаксиса к конкретному синтаксису.
Конкретный синтаксис включает в себя
средства для развернутого описания всех синтаксических элементов, вбирая всю
информацию абстрактного и лексического уровней.
Естественно, что грамматика конкретного синтаксиса должна быть согласована
с абстрактным синтаксисом. Это означает: правила подстановки выбирают так, что-
бы деревья разбора были как можно ближе к абстрактным синтаксическим деревьям.
Обработка ассоциативности и приоритетности.Все операции в языке С имеют разный приоритет приоритет.
Операция присваивания является правоассоциативной и имеет минимальным при-
оритет, все остальные операции —
левоассоциативные. Самый высокий приоритет имеют мультипликативные
операции(∗, / , %).
1. Для каждой строки таблицы операций (каждого уровня приоритета) выбирается
нетерминал.
2. Для факторов (или наименьших подвыражений) создается дополнительный
нетерминал.
3. Строки таблицы обрабатываются последовательно: начинают с первой, а за-
канчивают последней строкой. Для левоассоциативных операций строятся
леворекурсивные правила подстановки, для правоассоциативных операций —
праворекурсивные правила подстановки.
В каждой группе правил предусмотрено правило-заглушка, дающая запрет на
рост соответствующего списка.
Расширенная BNF.EBNF — расширение BNF, ориентированное на облегчение описания списков
и необязательных элементов. EBNF не предоставляет дополнительных возможно-
стей, поэтому все, что определяется в EBNF, может быть также определено в BNF.
Для представления списков важны следующие характеристики: нулевая длина,
роль разделителя элементов. Разделитель отделяет элементы, если он появляется
между ними. Разделитель завершает элементы, если он появляется после каждого
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
