Синтаксический анализ строк правил и обратное преобразование Python

Разбиение строк удобно использовать для деления текста на колонки, но эта операция также может использоваться как более универсальный инструмент синтаксического анализа — разбивая строку несколько раз, по разным разделителям, можно выполнить разбор более сложного текста. Анализ такого рода можно проводить с помощью более мощных инструментов, таких как регулярные выражения, с которыми мы познакомимся далее в этой главе, однако анализ на основе операции разбиения строки проще реализуется в виде быстро создаваемых прототипов, и, вполне возможно, он будет выполняться быстрее.

В примере 19.2 демонстрируется один из способов применения операций разбиения и объединения строк для синтаксического разбора предложений из простого языка. Он взят из основанной на правилах оболочки экспертной системы (holmes), которая написана на Python и включена в пакет примеров для книги (подробнее о holmes чуть ниже). Строки правил в системе holmes имеют вид:

"rule <id> if <test1>, <test2>… then <conclusion1>, <conclusion2>…"

Проверки и выводы являются конъюнкциями выражений («,» означает «и»). Каждое выражение является списком слов или переменных, разделенных пробелами; переменные начинаются с символа ?. Перед использованием правила оно переводится во внутренний формат — словарь с вложенными списками. Чтобы отобразить правило, оно переводится обратно в строковый формат. Например, для вызова:

rules.internal_rule(‘rule x if a ?x, b then c, d ?x‘) преобразование в функции internal_rule происходит, как показано ниже:

string = ‘rule x if a ?x, b then c, d ?x’

i = [‘rule x’, ‘a ?x, b then c, d ?x’] t = [‘a ?x, b’, ‘c, d ?x’] r = [», ‘x’] result = {‘rule’:’x’, ‘if’:[[‘a’,’?x’], [‘b’]], ‘then’:[[‘c’], [‘d’,’?x’]]}

Сначала выполняется разбиение по if, затем по then и наконец по rule. В результате получаются три подстроки, разделенные по ключевым словам. Подстроки проверок и выводов разбиваются сначала по «,», а затем по пробелам. Для обратного преобразования в исходную строку используется метод join. В примере 19.2 приводится конкретная реализация этой схемы.

Пример 19.2. PP4E\Lang\rules.py

def internal_rule(string):

i = string.split(‘ if ‘)

t = i[1].split(‘ then ‘) r = i[0].split(‘rule ‘) return {‘rule’: r[1].strip(), ‘if’:internal(t[0]), ‘then’:internal(t[1])}

def external_rule(rule): return (‘rule ‘ + rule[‘rule’] +

‘ if ‘ + external(rule[‘if’]) +

‘ then ‘ + external(rule[‘then’]) + ‘.’)

def internal(conjunct):

res = [] # ‘a b, c d’

for clause in conjunct.split(‘,’): # -> [‘a b’, ‘ c d’]

res.append(clause.split()) # -> [[‘a’,’b’], [‘c’,’d’]]

return res

def external(conjunct): strs = [] for clause in conjunct: # [[‘a’,’b’], [‘c’,’d’]]

strs.append(‘ ‘.join(clause)) # -> [‘a b’, ‘c d’] return ‘, ‘.join(strs) # -> ‘a b, c d’

В настоящее время для получения некоторых строк-выводов можно было бы использовать генераторы списков и выражения-генераторы. Функции internal и external, например, можно было бы реализовать так (смотрите файл rules2.py):

def internal(conjunct):

return [clause.split() for clause in conjunct.split(‘,’)]

def external(conjunct):

return ‘, ‘.join(‘ ‘.join(clause) for clause in conjunct)

В результате требуемые вложенные списки и строка обрабатываются за один шаг. Эта реализация, возможно, будет работать быстрее — я оставляю читателю право самому решить, какой из вариантов более сложен для понимания. Как обычно, компоненты этого модуля можно протестировать в интерактивной оболочке:

>>> import rules

>>> rules.internal(‘a ?x, b’)

[[‘a’, ‘?x’], [‘b’]]

>>> rules.internal_rule(‘rule x if a ?x, b then c, d ?x’)

{‘then’: [[‘c’], [‘d’, ‘?x’]], ‘rule’: ‘x’, ‘if’: [[‘a’, ‘?x’], [‘b’]]}

>>> r = rules.internal_rule(‘rule x if a ?x, b then c, d ?x’)

>>> rules.external_rule(r)

‘rule x if a ?x, b then c, d ?x.’

Это максимум того, что может предоставить подобный разбор путем разбиения строк по лексемам. Он не предоставляет прямой поддержки рекурсивной вложенности компонентов и довольно примитивно обрабатывает синтаксические ошибки. Но для задач анализа инструкций простых языков разбиения строк может оказаться достаточно, по крайней мере, для создания прототипов и экспериментальных систем. Потом всегда можно добавить более мощный механизм анализа правил или заново реализовать правила в виде программного кода или классов Python.

Подробнее об оболочке экспертной системы holmes

Как на практике можно применять эти правила? Как уже упоминалось, анализатор правил, с которым мы только что познакомились, входит в состав оболочки экспертной системы holmes. Holmes — довольно старая система, написанная в 1993 году, еще до появления версии Python 1.0. Она осуществляет прямой и обратный логический вывод согласно задаваемым правилам. Например, правило

rule pylike if ?X likes coding, ?X likes spam then ?X likes Python

можно использовать для проверки того, что любит ли некто Python (обрат ный вывод, от «then» к «if»), и для вывода о том, что некто любит Python, из множества известных фактов (прямой вывод, от «if» к «then»). Для логического вывода может использоваться несколько правил, состоящих из набора предложений, представленных в виде конъюнкции; правила, указывающие на одно заключение, представляют альтернативы. Система holmes также осуществляет попутно простой поиск по шаблону для присваивания значений переменным, имеющимся в правилах (например, ?X), и может объяснить свои выводы.

Использованная литература:

Марк Лутц — Программирование на Python, 4-е издание, II том, 2011