Разбор исходного кода C / C ++: как границы / взаимодействия токенов указаны в lex / yacc? - PullRequest
Новая
       12

Разбор исходного кода C / C ++: как границы / взаимодействия токенов указаны в lex / yacc?

4 голосов
/ 24 ноября 2010

Я хочу проанализировать некоторый код C ++, и в качестве руководства я смотрел здесь определения C lex / yacc: http://www.lysator.liu.se/c/ANSI-C-grammar-l.html и http://www.lysator.liu.se/c/ANSI-C-grammar-y.html

Я понимаю спецификациисами токены, но не то, как они взаимодействуют.например.нормально, чтобы оператор, такой как =, следовал непосредственно за идентификатором, не вставляя пробелы (т. е. "foo ="), но это не нормально, когда за числовой константой сразу следует идентификатор (т. е. 123foo).Однако я не вижу, чтобы такие правила были представлены.

Что мне не хватает? ... или этот lex / yacc слишком либерален в принятии ошибок.

Ответы [ 4 ]

3 голосов
/ 24 ноября 2010

Лексер преобразует поток символов в поток токенов (я думаю, это то, что вы подразумеваете под спецификацией токена). Грамматика указывает, какие последовательности токенов допустимы. Следовательно, вы не увидите, что что-то не разрешено; Вы видите только то, что разрешено. Имеет ли это смысл?

EDIT

Если цель состоит в том, чтобы заставить лексера отличать последовательность «123foo» от последовательности «123foo», то одним из способов является добавление спецификации для «123foo». Другой способ - считать пространства значимыми.

EDIT2

Синтаксическая ошибка может быть «обнаружена» из лексера или создания грамматики или более поздних стадий компилятора (например, ошибки типа, которые все еще являются «синтаксическими ошибками»). Я думаю, какая часть всего процесса компиляции обнаруживает, какая ошибка в значительной степени является проблемой проектирования (поскольку она влияет на качество сообщений об ошибках). В данном примере, вероятно, имеет больше смысла объявить вне закона «123foo» посредством токенизации на недопустимый токен, а не полагаться на отсутствие производства с числовым литералом, за которым следует идентификатор (по крайней мере, это НКУ).

1 голос
/ 24 ноября 2010

Лексер в порядке с 123foo и разделит его на два токена.

  • Целочисленная константа
  • и идентификатор.

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

Обратите внимание, что лексеру не важны пробелы (если вы явно не скажете ему об этом). В этом случае он просто выбрасывает пробел: 

[ \t\v\n\f]     { count(); } // Throw away white space without looking.

Просто чтобы проверить, что я построил: 

wget http://www.lysator.liu.se/c/ANSI-C-grammar-l.html > l.l
wget http://www.lysator.liu.se/c/ANSI-C-grammar-y.html > y.y

Отредактированный файл l.l для остановки в компиляторе с жалобой на необъявленные функции: 

#include "y.tab.h"

// Add the following lines
int  yywrap();
void count();
void comment();
void count();
int  check_type();
// Done adding lines

%}

Создайте следующий файл: main.c: 

#include <stdio.h>

extern int yylex();

int main()
{
    int x;
    while((x = yylex()) != 0)
    {
        fprintf(stdout, "Token(%d)\n", x);
    }
}

Построить это: 

$ bison -d y.y
y.y: conflicts: 1 shift/reduce
$ flex l.l
$ gcc main.c lex.yy.c
$ ./a.out
123foo
123Token(259)
fooToken(258)

Да, это разделило его на два токена.

0 голосов
/ 17 декабря 2010

Вы не сможете анализировать C ++ с помощью lex и yacc, так как это неоднозначная грамматика. Вам понадобится более мощный подход, такой как GLR или какое-нибудь хакерское решение, которое модифицирует лексер во время выполнения (именно так поступают большинство современных синтаксических анализаторов C ++).

Взгляните на Эльзу / Элькхаунд.

0 голосов
/ 24 ноября 2010

По сути дела, лексические правила для каждого типа токенов жадные.Например, последовательность символов foo= не может быть интерпретирована как один идентификатор, поскольку идентификаторы не содержат символов.с другой стороны, 123abc на самом деле является числовой константой, хотя и искаженной, поскольку числовые константы могут заканчиваться последовательностью буквенных символов, которые используются для выражения типа числовой константы.

...