как typedef-name - проблема с идентификатором решена в C?

Недавно я писал парсер для языка на основе C. Я использую CUP (Yacc для Java).

Я хочу реализовать «взлом лексера» (http://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-c%E2%80%99s-grammar-revisited/ или https://en.wikipedia.org/wiki/The_lexer_hack), чтобы различать имена typedef и переменные/ имена функций и т. д. Чтобы разрешить объявление переменных с тем же именем, что и объявленный ранее тип (пример из первой ссылки):

typedef int AA;

void foo() {
    AA aa;       /* OK - define variable aa of type AA */
    float AA;    /* OK - define variable AA of type float */
}

мы должны ввести несколько новых производств, где имя переменной/функции может быть либо IDENTIFIER, либо TYPENAME. И вот тут-то и возникают трудности — конфликты в грамматике.

Я пытался не использовать эту запутанную грамматику Yacc для gcc 3.4 (http://yaxx.googlecode.com/svn-history/r2/trunk/gcc-3.4.0/gcc/c-parse.y), но на этот раз у меня нет идея, как разрешать конфликты самостоятельно. Я взглянул на грамматику Yacc:

declarator:
    after_type_declarator
    | notype_declarator
    ;

after_type_declarator:
    ...
    | TYPENAME
    ;

notype_declarator:
    ...
    | IDENTIFIER
    ;

fndef:
    declspecs_ts setspecs declarator
    // some action code
    // the rest of production
...

setspecs: /* empty */
    // some action code

declspecs_ts означает Declaration_specifiers, где "был ли замечен спецификатор типа; после спецификатора типа имя typedef является идентификатором для повторного объявления (_ts или _nots)".

Из declspecs_ts мы можем добраться

typespec_nonreserved_nonattr:
    TYPENAME
    ...
    ;

На первый взгляд я не могу поверить, как не возникают конфликты сдвига/уменьшения! setspecs пусто, поэтому у нас есть declspecs_ts, за которым следует declarator, так что мы можем ожидать, что синтаксический анализатор должен запутаться, происходит ли TYPENAME из declspecs_ts или из declarator.

Может ли кто-нибудь объяснить это кратко (или даже точно). Заранее спасибо!

РЕДАКТИРОВАТЬ: полезная ссылка: http://www.gnu.org/software/bison/manual/bison.html#Semantic-Tokens


parsing compilation grammar context-sensitive-grammar
person Grzes    schedule 19.06.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я не могу говорить за конкретный код.

Но основная хитрость заключается в том, что лексер C проверяет каждый идентификатор IDENTIFIER и решает, может ли он быть именем определения типа. Если это так, то он меняет тип лексемы на TYPEDEF и передает ее синтаксическому анализатору.

Как лексеру узнать, какие идентификаторы являются определениями типов? По сути, синтаксический анализатор должен сообщать об этом, собирая информацию typedef во время работы. Где-то в грамматике, связанной с объявлениями, должно быть действие для предоставления этой информации. Я ожидал, что это будет связано с правилами грамматики для объявлений typedef.

Вы не показали, что делает "setspec"; может быть, это место. Обычный трюк, используемый с генераторами синтаксических анализаторов LR, состоит в том, чтобы ввести правило грамматики E с пустой правой рукой (ваш пример «setspec»?), Которое будет вызываться в середине какого-либо другого правила грамматики (ваш пример «fndef») только для того, чтобы включить доступ к семантическому действию в середине обработки этого правила.

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

person Ira Baxter    schedule 20.06.2013
comment
Вы правы, но в данном случае происходит нечто иное. Вы можете прочитать определение setspec в ссылке над фрагментом кода. Я посмотрел немного глубже в этот код. declspecs_ts содержит ТОЛЬКО ОДИН TYPENAME и часто некоторые другие спецификаторы (такие как INLINE и т. д.). Существуют также другие варианты, такие как declspecs_nots, и мы должны комбинировать разные declspecs с after_type_declarator и notype_declaraor для поддержки всех возможных комбинаций. Это еще сложнее (из-за атрибутов), тем не менее, это организовано/разделено достаточно разумно, чтобы предотвратить конфликты. - person Grzes; 20.06.2013
comment
Добро пожаловать в рабочие грамматики, в которых есть не только стандартные языковые конструкции, но и весь остальной мусор, который выбрасывает в кучу конкретный компилятор/диалект (например, GCC, MS, GreenHills). Когда вы добавляете все расширения, которые делают люди, грамматика перестает быть простой. Если вам повезет, грамматика все еще организована/разделена достаточно разумно, чтобы ею можно было управлять. Парсеры GLR на самом деле делают это для больших сложных грамматик немного проще, потому что им не нужно запутывать такие вещи, как TYPEDEF, проверяющие саму грамматику. - person Ira Baxter; 20.06.2013
comment
Вот как я это вижу: declspecs_ts after_type_declaration для случая, когда имя типа переобъявлено как переменная (возможно, какое-то другое имя типа2), например: typedef int myType1; typedef float myType2; { myType1 myType2; /* variable myType2 (name) of type myType1 */ } declspecs_nots notype_declaration для простого int foo; - person Grzes; 20.06.2013
comment
Хорошо, вы можете порекомендовать какой-нибудь парсер GLR для Java? - person Grzes; 20.06.2013
comment
Обратите внимание на strategoxt.org/Stratego/JSGLR У меня нет конкретного опыта в этом, но ребята из Stratego неплохой поступок. Не удивлюсь, если вы найдете поблизости грамматику Си. - person Ira Baxter; 20.06.2013