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

Question

Я недавно писал парсер для языка на основе 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 где «был ли видел спецификатор типа, после того, как спецификатор типа, имя ЬурейеЕ является идентификатором для переобъявить (_ts или _nots).»

От declspecs_ts мы можем достичь

typespec_nonreserved_nonattr: 
    TYPENAME 
    ... 
    ; 

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

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

EDIT: Полезные ссылки: http://www.gnu.org/software/bison/manual/bison.html#Semantic-Tokens

Answer 1

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

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

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

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

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