Syntactical analysis of monomials in context-free languages taking into account the productions application order.pdf Начальным объектом в теории формальных языков и грамматик является алфавит, разделённый на два подмножества, первое из которых образуют нетерминальные (вспомогательные) символы z\\,... ,zn, необходимые для задания грамматических правил, а второе - терминальные символы xi,... ,xm, образующие словарь языка [1, 2]. Практически все языки программирования принадлежат важному с точки зрения приложений классу контекстно-свободных языков (КС-языков). КС-язык определяется его грамматикой - совокупностью правил подстановки (продукций) (1) zj ^ qjk(z,x), j = 1,... ,n, k = 1,... ,pj, где qjk(z,x) -заданные мономы. Таким образом, грамматика КС-языка характеризуется тем, что один нетерминальный символ независимо от его окружения (контекста) заменяется на группу символов. Правила подстановки можно применять к начальному символу zi, а затем к другим символам в мономах неограниченное число раз в любом порядке, что позволяет выводить новые мономы, которые и образуют КС-язык. Проблема синтаксического анализа мономов (программ) КС-языка состоит в том, чтобы разработать алгоритм, позволяющий определить, можно ли вывести моном из начального символа с помощью заданных правил подстановки, а также определить, какие продукции и сколько раз были использованы при выводе этого монома. Известно, что для произвольной грамматики КС-языка беступикового алгоритма синтаксического анализа не существует, поэтому алгоритм синтаксического анализа достаточно сложен, поскольку предусматривает возвраты [1]. Традиционно считается, что порядок применения продукций устанавливать не требуется [1]. Однако без знания этого порядка невозможно вывести тот моном, который исследуется, поскольку применение продукций в различном порядке может приводить к разным мономам. В связи с этим предлагается расширить проблему синтаксического анализа следующим образом: разработать беступиковый алгоритм, позволяющий установить, можно ли вывести данный моном, какие продукции и сколько раз следует использовать, а также, если возможно, порядок применения этих продукций. Для того чтобы решить расширенную проблему синтаксического анализа, мы предлагаем не только включать в моном информацию о каждой использованной продукции в виде мономиальной метки [3, 4], но и устанавливать иерархию скобок (слева от открывающейся скобки всегда «привязана» мономиальная метка, а соответствующая закрывающаяся скобка может быть однозначно найдена); иерархия скобок позволяет определить порядок использования продукций. Рассмотрим «расширенную» грамматику для рассматриваемого КС-языка: zj ^ tjk[ qjk(z,x)], j = 1,... ,n, k = 1,... ,pj. Здесь tjk - символ из расширенного алфавита: мономиальная метка, соответствующая правилу вывода zj ^ tjk qjk (z,x) и «привязанная» слева к открывающейся скобке. Расширенная грамматика позволяет определять порядок применения продукций. Пример 1. Рассмотрим продукции z1 ^ z1z|, z1 ^ z1z2 и запишем их в виде расширенной грамматики: z1 ^ tn[ z^ ], z1 ^ t12[ z1z2 ]. Применяя к начальному символу первую продукцию, а затем вторую, получим моном tu[ t12[ z1z2 ] z| ]. Теперь можно видеть порядок применения продукций: внешние скобки показывают, что первая продукция с меткой t11 применена первой, а внутренние скобки - что вторая продукция с меткой t12, привязанной к отрывающейся скобке, применена во вторую очередь. Иерархия скобок позволяет установить порядок применения продукций и в общем случае. Для этого рассмотрим расширенную систему уравнений Хомского - Щутцен-берже, которая имеет вид zj = Q*j(z,x,t) d=f tj1[ qj1(z,x)}+ ... + j[ qjpj(z,x)], j = 1, ... ,n. (2) Решение этой системы можно получить методом последовательных приближений [2]: z(k+1)(x,t) = Q*(z(k)(x,t),x,t); k = 0,1,...; z(0) = 0. В результате решение получается в виде формальных степенных рядов те zj = z*(x, t) = Y,{z*j,Wi) Wi, j = 1,..., n, i=0 где Wi - мономы от символов x1,... ,xm,t11 ,t12,... ,tnpn с числовыми коэффициентами (z*,wi), содержащие также систему открывающихся и закрывающихся скобок. Считывая мономы соответствующей степени формального степенного ряда z1 (x,t) относительно символов x1,... , xm и пропуская символы t11,t12,..., tnpn, можно выяснить, есть ли среди них нужный моном [3, 4]. При этом мономиальные метки укажут на использованные продукции, а иерархия скобок установит порядок их использования (внутренние скобки соответствуют продукциям, которые использованы позже). Теорема 1. Решая расширенную систему уравнений Хомского - Щутценбер-же (2) методом последовательных приближений и считывая мономы нужной степени относительно терминальных символов, можно за конечное число шагов провести беступиковый синтаксический анализ (с учётом порядка применения продукций) любого монома КС-языка, заданного грамматикой (1).

Скачать электронную версию публикации