Вопрос по конечным автоматам

← →
Ломброзо © (2006-01-19 22:07) [0]

...то есть по GOLD парсер, на который меня любезно натравили unknown и Паша Голубь.
Как работает конечный автомат я в общих чертах представляю, но возникли сложности с пониманием терминологии Gold Parser, и, как следствие, алгоритма разбора дерева, получаемого на выходе работы парсера.

Итак, я понял, что два самых главных события, на которые я должен отреагировать во время работы парсера - это чтение лексемы (Token) и - второе - т.н. Reduction (в терминологии Gold Parser).
Вот что такое Reduction? Если можно, объясните, пожалуйста, на пальцах.

← →
TUser © (2006-01-19 22:26) [1]

Может правило ("сведЕние") в форме БН?, Т.е.
default_type ::= char|int|....

reduction 1) редукция; уменьшение; сокращение 2) предварительная обработка; предварительное преобразование, сжатие ( данных ) 3) превращение; приведение; сведение ( к чему-л. ); упрощение • - data reduction - graphic data reduction - industrial data reduction - innermost reduction - mission data reduction - network data reduction - network reduction - off-line data reduction - on-line data reduction - outermost reduction - priority data reduction - real-time data reduction - rowwise reduction - search reduction - variety reduction

← →
Ломброзо © (2006-01-19 22:32) [2]

>Может правило ("сведЕние")
Во-во, близко, в исходных кодах встречается фраза Reduction Rule. И это самое событие возникает в промежутке между событиями Token Read - когда парсер на запятую натыкается между идентификаторами, или ключевое слово встретилось... А вот закономерности уловить не могу.

Электронный переводчик у меня тоже есть, между прочим.

← →
Mystic © (2006-01-19 23:01) [3]

Ты понимаешь различие между восходящими и нисходящими схемами разбора?

При восходящей схеме выполняется два типа операций с потоком лексем: сдвиг (shift) и свертка (reduce). Например, рассмотрим входной поток

type TA = class(Exception) end;

для грамматики (жирным выделены слова)

type : type id = class inherited end ; interited : /* пусто */ | ( id interface_list ) interface_list : /*пусто */ | , id interface_list

← →
Mystic © (2006-01-19 23:13) [4]

Лексема: type (нет правило, кидаем лексему в стек)
Стек type
Shift

Лексема TA (нет правила)
Стек type TA
Shift

Лексема = (нет правила)
Стек type TA =
Shift

Лексема class (не правила)
Стек type TA = class
Shift

Лексема ( (неп правила)
Стек type TA = class (
Shift

Лексема Exception (нет правила)
Стек type TA = class ( Exception
Shift

Лексема )
Правило interface_list: /*пусто*/
Стек до type TA = class ( Exception )
Стек после type TA = class ( Exception interface_list )
Reduce

Правило inherited: (id interface_list )
Стек до type TA = class ( Exception interface_list )
Стек type TA = class interface_list
Reduce

Лексема end
Стек type TA = class interface_list end
Shift

Лексема ;
Правило type : type id = class inherited end ;
Стек type
Reduce

Соответственно при чтении лексем может быть либо ситуация shift, либо reduce. Если возможно несколько shift, то происходит shift --- нет проблем. А вот если возникает возможность shift и reduce (или reduce и reduce), то часть парсеров не разруливают таких проблем, точнее YACC выдает информацию о конфликте и выбирает решение в пользу следования более раннему правилу

← →
Mystic © (2006-01-19 23:15) [5]

Там опечатка в последних трех имеется в виду inherited вместо interface_list
:(

← →
Mike Kouzmine © (2006-01-19 23:22) [6]

Mystic © (19.01.06 23:13) [4] На первый взгляд shift и reduce не должно вызывать проблем, а вот reduce и reduce - очень даже.

Mystic ©

Ага, спасибо, кажется понял. Поправьте если что:

Иными словами, если представить себе дерево, то reduce - это операция, протвиоположная shift; reduce сигнализирует о том, что был произведён обход ветви, парсер готов к обходу следующей ветви, а разработчик должен проанализировать стек лексем?

> На первый взгляд shift и reduce не должно вызывать проблем,
> а вот reduce и reduce - очень даже.

Ну... теоретически проблему избежать возможно (надо заглянуть, какие лексемы идут следующими и в зависимости от этого выполнять либо reduce, либо shift). Но это (опять же теоретически) может привести у усложнению конечного автомата, реализующего такую логику. Если, например, количество состояний автомата, который в случае shirt/reduce конфликта выбирает первый путь, примерно O(N), где N --- количество правил, то у такого автомата, как описали вы, будет O(N^2) . Точные значения я не помню. Ряд генераторов синтаксических анализаторов в состоянии решить этот конфликт, часть --- нет.

> Ломброзо © (19.01.06 23:58) [7]

Ну.. не совсем понял терминологии... Reduce говорит о том, что для последних лексем в стеке можно применить одно из правил. И заменяет набор лексем на новую лексему согласно правилу. А Shift просто читает новую лексему из списке лексем.

> Reduce говорит о том, что для последних лексем в стеке можно применить одно из правил

Ну да, примерно так я и понял. Спасибо.

Вопрос по конечным автоматам Найти похожие ветки