По идее LR1 синтаксис перед развёрткой таблиц учитывает только один входной символ
Я не однократно в интернете читал что синтаксис C/C++ входит в LR1 и большего просмотра вперёд не нужно.
Тогда почему в одном месте в синтаксисе могут встречаться объявление переменных, объявление метки, начало математических выражений?
Ведь вначале у всех трёх стоит идентификатор. Как Бизон их парсит?

Или бизон как-то заносит их в одну таблицу?

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

VV>По идее LR1 синтаксис перед развёрткой таблиц учитывает только один входной символ

Не уверен, что понял вас. Но вообще — нет. Единичка не влияет на то, как строятся базовые таблицы реудкций/переходов. Она в первую очередь определяет то, сколько символов (токенов) вперед нужно посмотреть, чтобы выбрать между различными возможными редкуциями текущего состояния.

VV>Я не однократно в интернете читал что синтаксис C/C++ входит в LR1 и большего просмотра вперёд не нужно.

Вперед — не нужно. А что там происходит с текущим стеком разбора?

VV>Тогда почему в одном месте в синтаксисе могут встречаться объявление переменных, объявление метки, начало математических выражений?
VV>Ведь вначале у всех трёх стоит идентификатор. Как Бизон их парсит?

А чем оно мешает? LR — дерево строится "снизу вверх". Когда мы видим идентификатор, нам не нужно сразу знать, какое именно итоговое правило будет использоваться.

Если совсем примитивно, LR — это стековая машина. У нее есть две операции. Первая — положить токен на стек. Вторая — взять несколько токенов со стека (соответствующих правой части правила) и заменить их на один токен (левую часть правила). И для такого процесса не нужно уникальных префиксов. Например, следующая грамматика вообще разбирается LR0-парсером:

op := addop | subop
addop := identifier identifier '+'
subop := identifier identifier '-'

На входе 'a b +' мы сналача кладем a (identifier), потом b (identifer), потом '+'. По первому правилу [a, b, '+'] преобразуется в [addop], которое, в свою очередь, по последнему правилу преобразуется в [op].

Далее. Где может быть нужна единичка в грамматике? Ну например,

oneliner := label | math | vardecl
label := labelName ':'
math := identifier '+' identifier
vardecl := typeName varName ';'
labelName := identifier
typeName := identifier
varName := identifier

Допустим, на входе у нас 'txt:'. Первым идет txt (identifier). Мы кладем его на стек и получаем [txt]. Далее у нас несколько возможностей. Во-первых, мы можем сделать любую из трех редукций к labelName, typeName, varName. Во вторых, мы можем решить оставить элемент на стеке и положить туда следующий (вдруг оно потом редуцируется, например, там далее '+ tst'). Вот здесь-то и используется просмотр потока вперед (look ahead) на один символ. Парсер смотрит, что дальше идет ':'. В соответствии с таблицей, это может быть только в конексте label. Значит в нашей ситуации нужно применять редукцию по правилу "labelName := identifier" и в результате стек будет [labelName]. Потом туда добавится ':' ([labelName, ':']) пройдет редукция к label и потом к oneliner.

VV>Или бизон как-то заносит их в одну таблицу?

Ага. Вы недавно не проходили то, как детерминируются недетерминированные конечные автоматы? Что-то подобное и происходит. Состояние может быть сложным "в середине правила A или может правила Б или правила В" (и это для кажой позиции в стеке). А потом добавляется еще разметка. Т.е. в каких состояниях нужно сделать свертку вершины стека (и по какому правилу). Свертка приводит к новому состоянию на вершине (мы заменили один или несколько состояний), которое может допускать дальнейшую свертку. Просмотр вперед позволяет использовать для выбора в этом процессе следующие элементы ввода (т.е. отсутствующие на стеке).

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



M>

M>oneliner := label | math | vardecl
M>label := labelName ':'
M>math := identifier '+' identifier
M>vardecl := typeName varName ';'
M>labelName := identifier
M>typeName := identifier
M>varName := identifier
M>

слишком лёгкий пример... не наглядно (у label, math, vardecl один уровень вложенности)

а как выкрутится если math намного сложнее как в реальном синтаксисе
ну например:

[/code]
oneliner := label | math | vardecl
math := math1 '+' math1
math1 := math2 * math2
math2 := identifier | "-" identifier
label := labelName ':'
[/code]

такое Бизон будет парсить или нужно преобразовывать?

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

VV>слишком лёгкий пример... не наглядно (у label, math, vardecl один уровень вложенности)

А в чем смущает уровень вложенности? При вычислении first/follow уровень вложенности ни на что кроме количества операций и памяти не влияет.

VV>такое Бизон будет парсить или нужно преобразовывать?

А вот не помню я всех умолчаний и поведения при конфликтах. Скорее всего — сможет. Но проблемы здесь не с уровнем вложенности:

follow(oneliner) = { eof }
follow(math) = { eof }
follow(math1) = { eof, '+' }
follow(math2) = { eof, '+', '*' } 
follow(labelName) = { ':' }
follow(typeName) = { identifier }
follow(identifier) = { eof, '+', '*', ':', identifier }

Допустим, у нас на стеке [..., identifier]. У нас допускается свертка в typeName, labelName или math2. Но! У трех этих нетерминалов разные follow. И как раз в зависимости от look-ahead будет выбрано правило для редукции (look-ahead терминал на стек на данном шаге не переносится!). Правило будет выбрано такое, в котором следующий токен имеет смысл. Т.е. если там ':', то будет labelName. А если '+' или '*', то будет редукция к math2. И, возможно, дальнейшие редукции до math1/math/oneliner.

Теперь почему я не до конца уверен в том, что грамматика будет обработана. В правиле math2 у вас reduce/reduce конфликт. Допустим, у нас есть стек [..., '-', identifier]. В этом случае может быть редукция как по первой ветви правила (к [..., '-', math2]), так и по второй (к [..., math2]). Если я правильно помню, на практике в данном случае будет выбрано самое длинное правило (т.е. с минусом) и все будет работать.

Вообще при разговоре про LR(1) нужно помнить, что там могут быть различные таблицы. Например, там есть общие для всех LR-парсеров определения "потенциальных" правил. По сути, это некая композиция всех конечных автоматов, распознающих регулярные выражения вида '.*ABC' где ABC — правая часть какого-то правила. Состояния вычисляются на стеке символов (токенов) и определяют все правила, которые допустимы для редукции (вне зависимости от контекста). Там может быть много похожих состояний. Например, для грамматики выше будут как минимум состояния (labelName, typeName, math2/1) (только первая редукция из math2 допустима, там нет минуса перед идентификатором на вершине стека) и (labelName, typeName, math2/1, math2/2) (допустимы обе редукции из правила math2, на вершине '-' и identifier). Потом строятся таблицы, зависящие от look-ahead. Там для каждого варианта look-ahead написано, что делать. Это может быть shift, это может быть reduce по конкретному правилу.

Здравствуйте, maxkar,
честно говоря ничего не понял ...
Может подскажете что почитать?

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

VV>Здравствуйте, maxkar,
VV>честно говоря ничего не понял ...
VV>Может подскажете что почитать?

Могу

Если нужно кратко, есть конспект лекций по разбору. По терминологии можноество follow (в моем сообщении выше) будет соответствовать построению множества возможных первых символов аванцепочек. В бумажном виде грамматики (со связными темами вроде конечных автоматов) разбираются в Драконе Компиляторы: принципы, технологии и инструменты.

Если нет проблем с английским, можете посмотреть здесь. В 8-й части определяются FIRST и FOLLOW. В 9-й — различные вариации парсеров.

С точки зрения практики можно взглянуть на How to write your own LR(1) parsing tables (and generate them). Там тоже есть first/follow и даже код/таблицы небольшого парсера. Можно будет посмотреть и изучить.

Здравствуйте, maxkar!
Насколько я понимаю LR1 парсер просматривает 2 входных символа — один на вершине стека другой прямо из входного потока?
Или я неправильно понял?

C++ нельзя распарсить по теории.

#include <stdio.h>

template <class t>
class a {
    public:
    a() {
        printf("a ctor\n");
    }
};

class b {};

int main()
{
    // int a, b, c;
    
    a < b > c;

    return 0;
}

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

vsb>C++ нельзя распарсить по теории.

vsb> a < b > c;

нету присваивания, а если будет

d =  a < b > c;

то это уже не объявление переменный

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

vsb>>C++ нельзя распарсить по теории.

vsb>> a < b > c;

VVV>нету присваивания, а если будет
VVV>

VVV>d =  a < b > c; 
VVV>

VVV>то это уже не объявление переменный

Нет. Раскомментируй строчку и printf исчезнет. Присваивание тут не при чём. Как парсить эти токены — зависит от того, какие переменные с какими именами были объявлены в доступном scope. То бишь лексический анализ и синтаксический анализ в C++ смешаны и разделить их нельзя.

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

VVV>Насколько я понимаю LR1 парсер просматривает 2 входных символа — один на вершине стека другой прямо из входного потока?
VVV>Или я неправильно понял?

Мне кажется, вы слишком упрощаете понимание стека. Там недостаточно смотреть только на один символ. Там нужно смотреть на сложное состояние разбора, которое пытается распознавать конструкции. Давайте пример:

stmts := stmt ';'
stmt := fwdType | fwdVar | type | var
fwdType := 'type' identifier
fwdVar := 'var' identifier
type := 'type' identifier 'is' identifier
var := 'var' identifier '=' identifier

Здесь часть продукций очень похожа. И если смотреть только на вершину стека, будет неоднозначность. Что делать, если на вершине стека identifier и далее в потоке ';'? Без контекста не ясно, по какому правилу будет производиться свертка. При этом если смотреть на весь стек, проблем не будет: ['var', identifier] с ';' в качестве look-ahead даст нам fwdVar.

Можно даже взять

	грамматику bison 1
	%{ #include <stdio.h> #include <math.h> int yylex (void); void yyerror (char const *); %} %define api.value.type {double} %token TYPE VAR IS NUM IDENTIFIER %% /* Grammar rules and actions follow. */ stmts: stmt ';' stmt: fwdType | fwdVar | type | var ; fwdType: TYPE IDENTIFIER ; fwdVar: VAR IDENTIFIER ; type: TYPE IDENTIFIER IS IDENTIFIER ; var: VAR IDENTIFIER '=' IDENTIFIER %%

и посмотреть на выхлоп (есть ключик --html, есть -g).

Часть вывода (из --html):

Grammar
...

7 fwdVar → VAR IDENTIFIER
...

State 0
...
VAR shift, and go to state 2
...
stmts go to state 3
stmt go to state 4
fwdVar go to state 6
...



State 2

7 fwdVar → VAR • IDENTIFIER
9 var → VAR • IDENTIFIER '=' IDENTIFIER

IDENTIFIER shift, and go to state 10


State 4

1 stmts → stmt • ';'

';' shift, and go to state 12


State 6
3 stmt → fwdVar •

$default reduce using rule 3 (stmt)


State 10

7 fwdVar → VAR IDENTIFIER • [';']
9 var → VAR IDENTIFIER • '=' IDENTIFIER

'=' shift, and go to state 14

$default reduce using rule 7 (fwdVar)

При разборе нашего примера мы в какой-то момент получаем стек [<State 0>, VAR, <State 2>, IDENTIFIER, <State 10>] и следующий символ ';'. Для него нет правила сдвига и нет специальной редукции. Поэтому выполняется свертка по правилу 7. Она может затрагивать сразу несколько элементов. В результате одного шага мы получаем [<State 0>, fwdVar], нам нужно построить следующее состояние. Оно делается на базе известного (на стеке!) состояния и таблицы переходов. По таблице мы получаем [<State 0>, fwdVar, <State 6>]. В 6-м состоянии у нас только редукция, получаем [<State 0>, stmt]. Нам снова нужно положить новое состояние на вершину. По таблице это state 4, стек [<State 0>, stmt, <State 4>]. Вот здесь нам опять нужно посмотреть на входной символ (все тот же, что был в начале) и сделать shift. Дальше все будет в несколько шагов свернуто в stmts.

Как видите, парсер здесь — не просто конечный автомат, который смотрит на несколько символов. Каждый переход определяется автоматом. Но сам разбор — это не автомат. Он может возвращаться в "предыдущие" состояния (лежащие на стеке) и выполнять из них новые переходы порождая новые состояния.

Более того, парсер в некоторой степени отслеживает и контекст, в котором встречаются правила. Например

stmt := label stmt | expr
label := identifier ':'
expr := identifier | expr '?' expr ':' expr

Допустим, у нас на стеке [..., identifier] и дальше (look ahead) в потоке ':'. Что будем делать? Сдвинем двоеточие в поток, чтобы получился label? Или сделаем редукцию identifier в expression? Хотя при этом стоится машина состояний, в которой никаких конфликтов нет.

Я предлагаю вам самим взять

	грамматику bison 2
	%{ #include <stdio.h> #include <math.h> int yylex (void); void yyerror (char const *); %} %define api.value.type {double} %token TYPE VAR IS NUM IDENTIFIER %% /* Grammar rules and actions follow. */ stmt: label stmt | expr ; label: IDENTIFIER ':' ; expr: IDENTIFIER | expr '?' expr ':' expr ';' ; %%

, сгенерировать бизоном html-отчет и построить по нему подробно (по шагам) все состояния стека разбора. Например, для входов вида 'a', 'a: b', 'c?d:e;', 'b: c?d:e?f:g;;', 'a:b: c?d:e;?f:g;'

Здравствуйте, maxkar,
читаю драконью книгу и интернет
https://neerc.ifmo.ru/wiki/index.php?title=LR(1)-%D1%80%D0%B0%D0%B7%D0%B1%D0%BE%D1%80
както с SLR ещё понятно а вот LR1 или LALR совсем не догоняю ...
может есть чтото по понятнее?

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

VVV>Здравствуйте, maxkar,
VVV>читаю драконью книгу и интернет
Управжнения из книги делаете? Некоторые вещи становятся понятнее, когда сделаны руками. Это как ездить на велосипеде — можно выучить много теории, но она никогда полностью не заменит практику.

VVV>https://neerc.ifmo.ru/wiki/index.php?title=LR(1)-%D1%80%D0%B0%D0%B7%D0%B1%D0%BE%D1%80
Конкретно по ссылке материал не очень. Например, много опечаток (альфа и а перепутаны), некоторые утверждения вызывают много вопросов (в оригинале структура вроде другая).
Но зато там есть ссылка на курс с хорошими материалами. Там достаточно подробное описание и есть примеры грамматик, не разбираемых другими классами. Например, есть LR(1)-грамматика, не являющаяся SLR(1).

VVV>както с SLR ещё понятно а вот LR1 или LALR совсем не догоняю ...
Со слайдами выше должно стать получше. Вообще все эти вариации — уточнение и детализация правил разбора. LR(0) конфликтов/неоднозначностей не допускает. SLR допускает, но использует очень простой алгоритм разрешения. Например, если на стеке [..., a, b, c], в потоке следующий символ d и есть правила D -> abc, то свертка будет, если где-нибудь в грамматике за D может быть терминал d. "Где-нибудь" — это очень "слабое" условие. Может быть, контекст (символы слева) предполагают контекст, в котором за D не может следовать d. LR(n) как раз разрешает эту неоднозначность. Он к каждому правилу приписывает "контекст". В данном случае контекстом является следующий терминал (или несколько символов в случае LR(k)), которые могут следовать за состоянием (точнее, правилом) в каком-то валидном разборе. Т.е. [A->b•Cd, x] — это разбор нетерминала A (мы прочитали b и должен следовать нетерминал C) в контексте, когда после нетерминала A должен следовать терминал x. В данном случае для разбора C контекст A не очень важен — за C (в данном контексте) может следовать только d. Но если вдруг у нас есть правила вида [A->b•C, x] или [A->b•CD, x] (где D может порождать пустую цепочку), то x может определять свертку в C (в слайдах есть пример, это LR(1) не являющийся LALR(1)). LR-алгоритм является формализацией этой идеи.

LALR(1) — оптимизация LR(1). Она уменьшает количество состояний, но при этом теряет точность. Разницу можно посмотреть в том же bison. Он по умолчанию генерирует LALR но можно попросить делать LR.

VVV>может есть чтото по понятнее?
Привел выше слайды, с ними должно быть полегче. А вот что есть материалы сильно понятнее — сомневаюсь. Дракон и слайды для меня были достаточно понятны. Я не уверен, что можно где-то упростить объяснения. Практика (упражнения) могут помочь. Ну и дальше нужно смотреть, что именно у вас вызывает проблемы. Например, вы можете написать, какие задачи у вас вызвали сложности? Или что в процессе построения конечных автоматов не получилось? Или какую-то другую конкретику? Без обратной связи здесь сложно.

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

VV>По идее LR1 синтаксис перед развёрткой таблиц учитывает только один входной символ

Скорей токен.

VV>Я не однократно в интернете читал что синтаксис C/C++ входит в LR1 и большего просмотра вперёд не нужно.

Я так же неоднократно читал в интернете, что в C/C++ в паре мест есть неприятные исключения из этого правила,
поэтому парсеры C/C++ не чистые LR, а с разными хаками. Вот например первая ссылка: https://stackoverflow.com/questions/243383/why-cant-c-be-parsed-with-a-lr1-parser/1004737#1004737

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


M>Если совсем примитивно, LR — это стековая машина. У нее есть две операции. Первая — положить токен на стек. Вторая — взять несколько токенов со стека (соответствующих правой части правила) и заменить их на один токен (левую часть правила). И для такого процесса не нужно уникальных префиксов.

...

VV>>Или бизон как-то заносит их в одну таблицу?

M>Ага. Вы недавно не проходили то, как детерминируются недетерминированные конечные автоматы? Что-то подобное и происходит. Состояние может быть сложным "в середине правила A или может правила Б или правила В" (и это для кажой позиции в стеке). А потом добавляется еще разметка. Т.е. в каких состояниях нужно сделать свертку вершины стека (и по какому правилу). Свертка приводит к новому состоянию на вершине (мы заменили один или несколько состояний), которое может допускать дальнейшую свертку. Просмотр вперед позволяет использовать для выбора в этом процессе следующие элементы ввода (т.е. отсутствующие на стеке).

И тут мы куда-то ушли в строну. Согласно определению LR парсера процитированному выше -- он заменит согласно правилу и потом окажется не прав, что окончится ошибкой парсинга. И это именно что ДКА, а не НКА. Я понимаю, что НКА можно свести к ДКА (путём увеличения числа состояний и добавления "магазинной памяти"), но мне кажется это уже не LR парсер. Может быть GLR, но это другое.

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


fk0> И тут мы куда-то ушли в строну.
Здесь соглашусь с вами, там есть влияние бредовых идей. Писал по памяти, уже 20 лет прошло . Я основную схему вспомнил, а вот подробности разметки с учетом контекста — нет. На стеке парсер распознает не "любое" правило, а только те, которые допускаются контекстом.

fk0> Согласно определению LR парсера процитированному выше -- он заменит согласно правилу и потом окажется не прав, что окончится ошибкой парсинга.
В большинстве случаев он обнаружит конфликт на этапе построения грамматики и пожалуется об этом. Хотя да, мне кажется, можно построить пример, где подобное разрешение конфликта shift/reduce в "локальном" контексте приводит к тому, что в результате разбор завершается с ошибкой. Например, рассмотрим следующую грамматику:

grm: 
  magic
| stmts

magic:
  IDENTIFIER THEN ELSE IDENTIFIER

expr: IDENTIFIER

stmts: 
  expr
| stmts THEN expr

Бизон честно предупреждает о конфликте и генерирует сдвиг (shift) после идентификатора (LR(n) не генерирует свертку если есть shift). В результате он не сможет разобрать "IDENTIFIER THEN IDENTIFIER", которой сводится в stmts. Подобный пример будет и проблемой для SLR (вот они предпочитают свертку при возможности shift/reduce). У меня просто нет генераторов, на которых я могу это проверить. Для практических грамматик это обычно проблемой не является. Там shift/reduce бывает (if ... then if ... else ...), но к серьезным проблемам не приводит.

fk0> И это именно что ДКА, а не НКА. Я понимаю, что НКА можно свести к ДКА (путём увеличения числа состояний и добавления "магазинной памяти"), но мне кажется это уже не LR парсер.
Не не не, LR-парсеры — это не конечные автоматы. Это именно стековые машины. Возьмите описание любой машины (из лекций, сгенерированных бизоном). Там будут переходы по нетерминалам. Конечные автоматы (ни ДКА, ни НКА) такого просто не умеют, у них нетерминалы нигде возникнуть не могут. А вот на стеке они возникают в результате свертки по правилам. Таблица переходов и вообще обработка очень похожа на КА, но все же это не КА.

А "НКА-состояния" вообще возникают в LR по ходу построения. Например, для грамматики:

grm: 
  stra
| strb

stra:
  VA VA VB

strb:
  VA VB VB

генерируется состояние вида

State 1
3 stra → VA • VA VB
4 strb → VA • VB VB

Да, это состояние ДКА "мы еще не решили, что это stra или strb". И оно соответствует композиции двух состояний НКА — "мы разбираем stra" и "мы разбираем strb".

fk0> Может быть GLR, но это другое.
GLR — да, это другое. Вот они как раз могут разрешать reduce/reduce конфликты и вести себя лучше в shift/reduce. Но это дополнительные надстройки над уще существующим стековым разбором.