Парсеры LR(1) С/C++

Тема в разделе "WASM.LANGS", создана пользователем _evil, 8 мар 2022.

Метки:
  1. _evil

    _evil Member

    Публикаций:
    0
    Регистрация:
    28 сен 2003
    Сообщения:
    57
    Подскажите парсеры С++ строят абстрактно синтаксическое дерево зная имена всех типов или нет?

    то есть если написано
    int a;
    то при обработке парсером он знает что это тип?
     
  2. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    4.861
    Ну, обычно информация о типах в компиляторах появляется на этапе семантической проверки, позже парсинга. Можно, конечно, погуглить на эту тему, но после парсинга у тебя будут только идентификаторы, и в случае с int кейворды.
     
  3. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    266
    Из-за шаблонов в целом это нетривиально, например существует такой забавный факт, что парсинг программы на C++ алгоритмически неразрешим: https://blog.reverberate.org/2013/08/parsing-c-is-literally-undecidable.html
    Звучит весьма грозно и страшно, но на деле это означает, что можно состряпать из шаблонов зацикленную шнягу, которая на абстрактной машине Тьюринга зациклится/зависнет, а реальный компилятор выплюнет ошибку компиляции из-за превышения некой максимальной (заданной авторами компилятора) глубины вложенности шаблонов.
    Но в целом да, АСД делается и замуты с шаблонами решаются.
     
  4. _evil

    _evil Member

    Публикаций:
    0
    Регистрация:
    28 сен 2003
    Сообщения:
    57
    Современные компиляторы выводят все ошибки по парядку (а не сначало ошибки лексера, потом парсера, потом генерации кода)
    Что наводит на мысль что парсер как-то объединён с генератором кода.
     
  5. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    4.861
    Лол! Конечно нет.
     
  6. _evil

    _evil Member

    Публикаций:
    0
    Регистрация:
    28 сен 2003
    Сообщения:
    57
    а почему?
     
  7. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    4.861
    Ну потому что. Смотрел хоть один компилятор в последние лет 15? Между лексером и кодогенератором там столько независимых друг от друга фаз может быть. Вообще, приведи пример, о какой конкретно ошибке ты говоришь.
    --- Сообщение объединено, 20 мар 2022 ---
    Образно, не обязательно прям такой порядок, но: Лексер -> Парсер -> Проверка семантики -> Оптимизация AST (много независимых фаз) -> Генерация IR (GIMPLE в GCC, LLVM IR в Clang) -> Тонна разных оптимизаций, независимых друг от друга -> Генератор кода. Фейлить у тебя обычно будут первые три этапа. Хотя не знаю, что можно написать, чтобы именно лексер прям зафейлил.
     
    Последнее редактирование: 20 мар 2022
  8. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    266
    Проверил у себя на GCC и ничего подобного. Ошибка препроцессора, например, прерывает компиляцию и до ошибок компилятора даже не доходит.
     
  9. _evil

    _evil Member

    Публикаций:
    0
    Регистрация:
    28 сен 2003
    Сообщения:
    57
    ну наприсер:
    t++t++a; //ошибка смантики
    a=" //незакрытая скобка
    все ошибки выводятся попорядку
     
  10. aa_dav

    aa_dav Active Member

    Публикаций:
    0
    Регистрация:
    24 дек 2008
    Сообщения:
    266
    Проверил - и да, действительно GCC выводит несколько ошибок, но как раз не по порядку.

    Сперва он ругается на незакрытую скобку, а потом на ошибку семантики и в моём случае еще одна ошибка под незакрытой скобкой.
    Т.е. сперва ругнулся лексер, но он всё-равно то что смог наскрести отправил в парсер и далее уже ругается еще и парсер.
     
    _evil нравится это.
  11. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    4.861
    Код (Text):
    1.  
    2. #include <stdio.h>
    3. int main(int argc, char** argv) {
    4. int t = 0;
    5. int a = 0;
    6. char* s = NULL;
    7.  
    8. a = t++t++a;
    9.  
    10. s = "
    11. }
    12.  
    Код (Text):
    1.  
    2. test.c: В функции «main»:
    3. test.c:8:12: ошибка: expected «;» before «t»
    4.     8 |     a = t++t++a;
    5.       |            ^
    6.       |            ;
    7. test.c:10:9: предупреждение: отсутствует завершающий символ "
    8.    10 |     s = "
    9.       |         ^
    10. test.c:10:9: ошибка: отсутствует терминирующий символ "
    11. test.c:11:1: ошибка: expected expression before «}» token
    12.    11 | }
    13.       | ^
    14.  
    Так а чего ему все ошибки не выводить и не делать это по порядку? Ворнинг исходит от препроцессора, так как тот тоже на токены пытается разбивать код. Остальные - ошибки парсера. Причем тут вообще семантика и тем более генератор кода? Просто в принципе нет узла AST для t++t++a, во что он должен был это распарсить по вашему, как это должно было дойти до проверки семантики и других этапов? Или вопрос в том, почему лексер не зафейлил?
    --- Сообщение объединено, 26 мар 2022 ---
    https://github.com/gcc-mirror/gcc/blob/16e2427f50c208dfe07d07f18009969502c25dc8/libcpp/lex.c#L2078 - хотя, может быть для C/C++ лексеров - это нормально, что нет закрывающей кавычки. CPP_DL_PEDWARN - по-умолчанию предупреждение, ошибка только при -pedantic-errors или -Werror: https://github.com/gcc-mirror/gcc/b...8009969502c25dc8/libcpp/include/cpplib.h#L574 (если он не видит терминирующую кавычку, то тип токена просто становится CPP_OTHER вместо строки или символа, и эту ситуацию, видимо, парсер должен разруливать).
    --- Сообщение объединено, 26 мар 2022 ---
    Код (Text):
    1.  
    2. # gcc -pedantic-errors test.c
    3. test.c: В функции «main»:
    4. test.c:8:12: ошибка: expected «;» before «t»
    5.     8 |     a = t++t++a;
    6.       |            ^
    7.       |            ;
    8. test.c:10:9: ошибка: отсутствует завершающий символ "
    9.    10 |     s = "
    10.       |         ^
    11. test.c:10:9: ошибка: отсутствует терминирующий символ "
    12. test.c:11:1: ошибка: expected expression before «}» token
    13.    11 | }
    14.       | ^
    15.  
    Предупреждение превратилось в ошибку, но все равно токен дошел до парсера и там же стал ошибкой второй раз.
     
    Последнее редактирование: 26 мар 2022
    _evil нравится это.