разбор — разрешение неоднозначности при создании синтаксического анализатора C ++
Я написал анализатор LALR (1) для C ++ 17. я нашел 156 двусмысленности, некоторые из них я могу решить в соответствии со стандартом, но другие я не могу.
Например:
Конфликт Shift-Reduce возникает при разбореоператор + < ……» когда меньше, чем встречается:
Мы можем разобрать это как:
(1)
идентификатор шаблона -> идентификатор оператора · < ……>
или же:
(2)
неполный идентификатор -> идентификатор оператора-функции ·
где (1) нужно сместить, но (2) нужно уменьшить.
Тем не менее, стандарт имеют:
После того, как name lookup (3.4) обнаружит, что имя является именем шаблона или что идентификатор оператора-функции или идентификатор оператора ссылается на набор перегруженных функций, любой член которых является шаблоном функции, если за ним следует <, < всегда принимается как разделитель списка аргументов шаблона и никогда не используется как оператор меньше. При анализе списка аргументов шаблона первое не вложенное> 137 принимается как конечный разделитель, а не как оператор больше чем.
Поэтому мы решили перейти.
К сожалению, есть много неясностей, я не могу найти решение. Здесь я перечислю некоторые из них (некоторые из них могут определенно сделать выбор, но я просто не могу найти доказательства):
- Есть ли какая-то часть в стандарте, которая указывает, что «сдвиг» является выбором по умолчанию, когда возникает неоднозначность?
описатель
(1) когда noptr-декларатор анализируется и встречается левосторонний, я должен уменьшить его в соответствии с:
ptr-декларатор -> noptr-декларатор ·
или сдвиньте левую часть, чтобы удовлетворить:
декларатор -> noptr-декларатор · Параметры и-классификаторы
параметры и квалификаторы -> · left-paren параметр-объявление-предложение right-paren ……
(2) когда идентификатор декларатора анализируется и встречается левая скобка, я должен уменьшить его в соответствии с:
noptr-декларатор -> декларатор-идентификатор ·
noptr-декларатор -> noptr-декларатор · \ left-скобка? константа-выражение \ правая скобка? атрибут-спецификатор-seq
или сдвиньте левый квадрат, чтобы удовлетворить:
noptr-декларатор -> декларатор-идентификатор · атрибут-спецификатор-seq
(атрибут-спецификатор-seq равен [[…….]])
Решение
В продолжение комментария TonyD: см. Почему C ++ не может быть проанализирован с помощью парсера LR (1)?
В некоторых местах вам, по сути, приходится сохранять неоднозначность, возникающую при разборе, и разрешать ее с помощью разрешения имен, или же эквивалентно, вы должны запутать разрешение имен в процессе разбора. В любом случае вы должны интерпретировать стандарт, чтобы определить, как следует разрешать неоднозначности, и да, это очень сложная задача.
Тогда вы узнаете, что такое компиляторы действительно делать; и GCC, и MS имеют множество расширений и отклонений от стандарта, как с точки зрения синтаксиса, так и семантических интерпретаций (они создают программы, которые дают разные результаты при разных компиляторах). Наконец, вы можете найти то, что мерзости в системных заголовочных файлах; это хаки, добавленные людьми компилятора, чтобы сделать их жизнь удобной, и очень плохо документированы, если вообще.
Другие решения
C ++ это Тьюринг завершен для разбора.
Очень актуальный пост Вот.