Здравствуйте, Курилка, Вы писали:

К>Вопрос несколько в сторону — на чём будет парсер написан? У Володи на плюсах вариант вроде бы как...
Риторический вопрос

Здравствуйте, ansi, Вы писали:

A>Здравствуйте, Курилка, Вы писали:

К>>Вопрос несколько в сторону — на чём будет парсер написан? У Володи на плюсах вариант вроде бы как...
A>Риторический вопрос

А мне казалось, что риторический вопрос: "Будет написан?"

Здравствуйте, eao197, Вы писали:

К>>>Вопрос несколько в сторону — на чём будет парсер написан? У Володи на плюсах вариант вроде бы как...
A>>Риторический вопрос

E>А мне казалось, что риторический вопрос: "Будет написан?"
E>

Ну тогда они оба риторические. Итого, имеем:

Парсер будет не написан на C#

Подборка статей и книг.
1. Parsing Techniques A Practical GuideОчень неплохой учебник.
2. Very Fast YACC-Compatible Parsers (For Very Little Effort)Интересная статья о оптимизации LR парсеров — замена парсера , основанного на таблицах на hardcoded автомат дало выиигрыш по быстодействию до 6 раз (по сравнению с бизоном)
3. Faster Generalized LR Parsing (1999)Оптимизация алгорита Томиты за счет уменьшения манипуляций со стеком.
4,5. Construction of Efficient Generalized LR Parsers (1997) Efficient Tabular LR ParsingЕще GLR. Ваши комментарии?
6. Practical LR Error Recovery.

А можно pdf или ps версию ?

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, little_alex, Вы писали:

_>>Здесь лежит GLR парсер генератор (напиcан на С++).
_>>И рабочий парсер C++ граматики.
_>>Документация



M>И еще одно: он, вероятно, некорректен. Парень этот писал алгоритм по дисику 1992 года, а только в 2000 была придумана версия алгоритма Томиты, которая все без исключения грамматики корректно обрабатывает. Главное в этой версии — модификация LR-автомата. Код неохота смотреть, но вряд ли он это делает.

Вот что ответил автор:

> How elkhound does handle epsilon rule?
> Documentation is silent about this.
Elkhound can handle any context-free grammar, including those with
epsilon rules.
> Does elkhound suffer from problems described is this paper
>
http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps?

The Elkhound implementation was originally based on the description in
Rekers' PhD thesis, which uses Farshi's solution to the hidden left
recursion problem.  As such, like Farshi's algorithm, for highly ambiguous
grammars, it can perform poorly (polynomial of degree as high as the
longest rule) due to the link search.

Johnstone's modification to Farshi (5.3 of the above link) isn't suitable
because the constant-factor costs of maintaining GSS precessor links is
prohibitve; one of Elkhound's goals is to be competitive with Bison for
LALR (fragments of) grammars, so the constant factors have to be kept to a
minimum.  Unfortunately, that means the asymptotic costs for some (very
non-LALR) grammars are higher than they otherwise could be.

I have studied Johnstone's right-nulled parser approach (section 6, and
later publications) somewhat, but still have concerns about the ability to
properly execute user-defined actions in that scheme.  I would have to
implement it myself to really explore it, and have not done so.

-Scott

Добавлено более подробное описание алгоритма и сравнение с другими реализациями GLR

Здравствуйте, little_alex, Вы писали:

M>>И еще одно: он, вероятно, некорректен. Парень этот писал алгоритм по дисику 1992 года, а только в 2000 была придумана версия алгоритма Томиты, которая все без исключения грамматики корректно обрабатывает. Главное в этой версии — модификация LR-автомата. Код неохота смотреть, но вряд ли он это делает.

_>Вот что ответил автор:
_>[code]
>> How elkhound does handle epsilon rule?
>> Documentation is silent about this.
_>Elkhound can handle any context-free grammar, including those with
_>epsilon rules.
>> Does elkhound suffer from problems described is this paper
>>
_>http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps?

_>The Elkhound implementation was originally based on the description in
_>Rekers' PhD thesis, which uses Farshi's solution to the hidden left
_>recursion problem. As such, like Farshi's algorithm, for highly ambiguous
_>grammars, it can perform poorly (polynomial of degree as high as the
_>longest rule) due to the link search.

Ага, ясно, автор использовал алгоритм Фарши. Я описывал его в моей статье . алгоритм работает корректно, но к сожалению, очень медленный.

_>Johnstone's modification to Farshi (5.3 of the above link) isn't suitable
_>because the constant-factor costs of maintaining GSS precessor links is
_>prohibitve; one of Elkhound's goals is to be competitive with Bison for
_>LALR (fragments of) grammars, so the constant factors have to be kept to a
_>minimum. Unfortunately, that means the asymptotic costs for some (very
_>non-LALR) grammars are higher than they otherwise could be.

_>I have studied Johnstone's right-nulled parser approach (section 6, and
_>later publications) somewhat, but still have concerns about the ability to
_>properly execute user-defined actions in that scheme. I would have to
_>implement it myself to really explore it, and have not done so.

Честно говоря, не совсем понятно, что автор имеет ввиду. Главная идея Джонстона состоит в том, чтобы модифицировать LR-атвомат так, чтобы там, где существуют эпсилон-правила, были переходы по этим символам в это же состояние. Тогда исчезают, как показал Джонстон, проблемы с цепными с некорректным разбором. Алгоритм, который приводил Джонстон, ничего особенного и отличного от алгоритма Томиты в себе не содержит, поэтому его можно просто не брать в расчет. Автор пишет, что одной из целей было "to be competitive with Bison for LALR (fragments of) grammars", видимо поэтому он не стал это реализовывать. Но и это тоже непонятно, такая модификация LR-автомата может быть проведена только для грамматик с эпсилон правилами, которые, как известно, не могут быть обработаны бизоном. Последний абзац наводит на мысль, что автор просто пока еще не вчитался в статью и не понял идеи Джонстона.

Здравствуйте, mefrill, Вы писали:

> Но и это тоже непонятно, такая модификация LR-автомата может быть проведена только для грамматик с эпсилон правилами, которые, как известно, не могут быть обработаны бизоном.


Разве гамматики с эпсилон правилами не являются LALR ?

Здравствуйте, little_alex, Вы писали:

_>Разве гамматики с эпсилон правилами не являются LALR ?

Ну да, там же неоднозначность. Если в каком-нибудь состоянии LR-автомата есть правило с точкой перед эпсилон-символом, то значит должна быть свертка по этому символу в это же состояние. Если есть переход по какому-нибудь другому символу, то имеем конфликт вида переход\свертка. Иначе, должна быть свертка по какому-то другому правилу, не эпсилон, т.е. имеем конфликт свертка\свертка.

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, little_alex, Вы писали:

_>>Разве гамматики с эпсилон правилами не являются LALR ?

M>Ну да, там же неоднозначность. Если в каком-нибудь состоянии LR-автомата есть правило с точкой перед эпсилон-символом, то значит должна быть свертка по этому символу в это же состояние. Если есть переход по какому-нибудь другому символу, то имеем конфликт вида переход\свертка. Иначе, должна быть свертка по какому-то другому правилу, не эпсилон, т.е. имеем конфликт свертка\свертка.

%token id

%start S
%%
S: A;

A:   B '+' A  
   | B; 
   
B:   '(' A ')'
   |  id
   | ;

что-то вроде (a+b+c+())+(v+w+z)
Bison.Никаких конфликтов нет.
?

Здравствуйте, little_alex, Вы писали:

_>

_>%token id

_>%start S
_>%%
_>S: A;

_>A:   B '+' A  
_>   | B; 
   
_>B:   '(' A ')'
_>   |  id
_>   | ;
_>

_>что-то вроде (a+b+c+())+(v+w+z)
_>Bison.Никаких конфликтов нет.
_>?

Ну как же нет? в состоянии

A --> * B '+' A
A --> * B

у тебя будет переход по символу B в состояние

A --> B * '+' A
A --> B *

Теперь, здесь у тебя конфликт свертка по правилу A --> B\сдвиг по символу '+'.

Иначе говоря, B у тебя выводится как при прочтении теримнала id, так и просто без его прочтения. Т.е. допустима строка +b+c.

Здравствуйте, mefrill, Вы писали:


M>Ну как же нет? в состоянии

M>A --> * B '+' A
M>A --> * B

M>у тебя будет переход по символу B в состояние

M>A --> B * '+' A
M>A --> B *

M>Теперь, здесь у тебя конфликт свертка по правилу A --> B\сдвиг по символу '+'.

свертка по A выполняется если только следующей символ $ или ')'
сдвиг выполняется если только следующей символ '+'



bison конфликтов не нашел

Здравствуйте, little_alex, Вы писали:

_>Здравствуйте, mefrill, Вы писали:


M>>Ну как же нет? в состоянии

M>>A --> * B '+' A
M>>A --> * B

M>>у тебя будет переход по символу B в состояние

M>>A --> B * '+' A
M>>A --> B *

M>>Теперь, здесь у тебя конфликт свертка по правилу A --> B\сдвиг по символу '+'.

_>свертка по A выполняется если только следующей символ $ или ')'
_>сдвиг выполняется если только следующей символ '+'

А по B?

_>bison конфликтов не нашел

Я не помню уже, код бизона смотрел достаточно давно. Но, по-моему, он просто эпсилон-правила игнорирует. Проверить неоднозначности можно вручную построив LR-автомат. Советую тебе это проделать для данной грамматики и увидишь в чем проблема.

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, little_alex, Вы писали:

_>>Здравствуйте, mefrill, Вы писали:


M>>>A --> B * '+' A (5)
M>>>A --> B *

M>А по B?

Терминальные символы, следующие за нетерминалом A, это ) $
Другие в корректном входном потоке быть не могут.
Соответственно в состояние 5 если lookahead равен '+' выполняем перенос,а если ) $ делаем свертку A-->B

Грамматика
    0 $accept: S $end
    1 S: A
    2 A: B '+' A
    3  | B
    4 B: '(' A ')'
    5  | id
    6  | /* пусто */

Терминальные символы с правилами, в которых они появляются

$end (0) 0
'(' (40) 4
')' (41) 4
'+' (43) 2
error (256)
id (258) 5

Нетерминальные символы с правилами, в которых они появляются

$accept (7)
    налево: 0
S (8)
    налево: 1, направо: 0
A (9)
    налево: 2 3, направо: 1 2 4
B (10)
    налево: 4 5 6, направо: 2 3


состояние 0
    0 $accept: . S $end
    id   shift, and go to state 1
    '('  shift, and go to state 2
    $default  reduce using rule 6 (B)
    S  go to state 3
    A  go to state 4
    B  go to state 5

состояние 1
    5 B: id .
    $default  reduce using rule 5 (B)

состояние 2
    4 B: '(' . A ')'
    id   shift, and go to state 1
    '('  shift, and go to state 2
    $default  reduce using rule 6 (B)
    A  go to state 6
    B  go to state 5

состояние 3
    0 $accept: S . $end
    $end  shift, and go to state 7

состояние 4
    1 S: A .
    $default  reduce using rule 1 (S)

состояние 5
    2 A: B . '+' A
    3  | B .
    '+'  shift, and go to state 8
    $default  reduce using rule 3 (A)

состояние 6
    4 B: '(' A . ')'
    ')'  shift, and go to state 9

состояние 7
    0 $accept: S $end .
    $default  accept

состояние 8
    2 A: B '+' . A
    id   shift, and go to state 1
    '('  shift, and go to state 2
    $default  reduce using rule 6 (B)
    A  go to state 10
    B  go to state 5

состояние 9
    4 B: '(' A ')' .
    $default  reduce using rule 4 (B)

состояние 10
    2 A: B '+' A .
    $default  reduce using rule 2 (A)

Здравствуйте, little_alex, Вы писали:

Неохота разбираться. Во-первых, Для строки "+a" будет вывод в этой грамматике

S ==> A ==> B + A ==> + A ==> + B ==> + id

Так что, грамматика у тебя немного не то определяет.

Во-вторых, обрати внимание на состояния

состояние 0
0 $accept: . S $end
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
S go to state 3
A go to state 4
B go to state 5

состояние 1
5 B: id .
$default reduce using rule 5 (B)

состояние 2
4 B: '(' . A ')'
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
A go to state 6
B go to state 5

С какой стати здесь свертка делается только по символу $? Почему по символу "(" ее не делать? Что это за "$default" такое? Откуда взялось?

Здравствуйте, mefrill, Вы писали:


M>Так что, грамматика у тебя немного не то определяет.
А я и не писал что она определяет.Прсто это пример гмамматики с eps правилами успешно разбараемой LALR(1).
Совсем простой пример

S-->B c;
B--> a|eps;

M> Что это за "$default" такое? Откуда взялось?

Это оптимизация таблиц — в красном драконе это вроде есть.
$default — все остальные терминалы ( все оставшиеся возможности )
Пусть терминалы -id + ( ) $
Тогда
( — shift ...
$default -reduce ...
под $default имеют ввиду id + ) $
Зачастую $default содержит больше терминалов, чем необходимо, то есть парсер делает reduce даже
в том случае если до оптимизации в таблице действия не было (то есть было действие-ошибка)

Здравствуйте, little_alex, Вы писали:

M>> Что это за "$default" такое? Откуда взялось?

_>Это оптимизация таблиц — в красном драконе это вроде есть.
_>$default — все остальные терминалы ( все оставшиеся возможности )
_>Пусть терминалы -id + ( ) $
_>Тогда
_>( — shift ...
_>$default -reduce ...
_>под $default имеют ввиду id + ) $
_>Зачастую $default содержит больше терминалов, чем необходимо, то есть парсер делает reduce даже
_>в том случае если до оптимизации в таблице действия не было (то есть было действие-ошибка)

состояние 2
4 B: '(' . A ')'
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
A go to state 6
B go to state 5

А почему свертка на "(" и "id" не делается? Откуда парсер вывел, что на этот символ свертку нельзя делать? Вообще,в LR-анализе свертка делается безусловно, не на какой-то символ. Вот, здесь, очевидно, бизон хитрит и делает всевозможные сдвиги, а затем "для остальных" терминалов оставляет свертку. Это жульничество и грамматика, которая была введена в генератор, и грамматика, для которой был построен разборщик, разные. Конфликт существет, но бизон его маскирует, выбирая сдвиг в качестве приоритета. Т.е. конфликт налицо и парсер работате некорректно.

Здравствуйте, mefrill, Вы писали:

M>состояние 2
M>4 B: '(' . A ')'
M>id shift, and go to state 1
M>'(' shift, and go to state 2
M>$default reduce using rule 6 (B)
M>A go to state 6
M>B go to state 5

M>А почему свертка на "(" и "id" не делается? Откуда парсер вывел, что на этот символ свертку нельзя делать? Вообще,в LR-анализе свертка делается безусловно, не на какой-то символ.

Это не верно. LR(0) действительно не использует предпросмотр вообще. Но LR(1) и LALR(1) используют предпросмотр прежде чем сделать
свертку равно как и перенос.
В данном примере за B может быть только + ) $ — соответственно делать свертку по B если во входном потоке другой символ бессмысленно.

Здравствуйте, little_alex, Вы писали:

_>Здравствуйте, mefrill, Вы писали:

M>>состояние 2
M>>4 B: '(' . A ')'
M>>id shift, and go to state 1
M>>'(' shift, and go to state 2
M>>$default reduce using rule 6 (B)
M>>A go to state 6
M>>B go to state 5

M>>А почему свертка на "(" и "id" не делается? Откуда парсер вывел, что на этот символ свертку нельзя делать? Вообще,в LR-анализе свертка делается безусловно, не на какой-то символ.

_>Это не верно. LR(0) действительно не использует предпросмотр вообще. Но LR(1) и LALR(1) используют предпросмотр прежде чем сделать
_>свертку равно как и перенос.

Ты попутал предостмотр и переход по символу. За символом B в данном случае может идти как '+', так и '(' и 'id'. Еще раз говорю, построй LR-автомат и увидешь проблему. Иначе, разговор беспредметный — ты говоришь о том, чего не знаешь. Ты ведь не строил LR-автоматов?

_>В данном примере за B может быть только + ) $ — соответственно делать свертку по B если во входном потоке другой символ бессмысленно.

А что LR-анализатор уже мыслить начал??? Ты представление об алгоритме построения LR(k)-автомата имеешь? Ну зачем спорить до уср-ки о том, в чем не разбираешься?

Здравствуйте, mefrill, Вы писали:
Спорить действительно больше не стоит.

Но всетаки открой книжку Parsing Techniques A Practical Guide и посмотри 210 стр. —
LR(1) with eps-rules . Fortunately LR(1) parses are strong enough to handle them without problems.