Дифференциация между ">>" и ">" при разборе общих типов

Ответ 1

При анализе языка обычно два основных компонента: сканер и синтаксический анализатор. Сканер создает поток токенов, и синтаксический анализатор интерпретирует этот поток на основе grammar, который является формальным определением правил производства в язык - вы можете найти грамматику для С# 4.0 здесь.

Отказ от ответственности: я не подразумеваю, что следующее, как язык С#, обрабатывается, я просто использую фрагмент С#, чтобы проиллюстрировать общие понятия.

Сканирование

Итак, первым шагом является создание токенов для синтаксического анализатора. Токены обычно будут иметь какой-то символический тип (указывающий тип маркера), лексему (фактический текст маркера) и, возможно, другую информацию, такую ​​как номер строки (полезной для обработки ошибок).

Итак, если мы используем List<Nullable<int>> list; из вашего вопроса в качестве примера, сканер выдаст следующие токены:

available_identifier, List
<
available_identifier, Nullable
<
integral_type, int
>
>
available_identifier, list
;

Обратите внимание, что типы токенов выводятся из грамматики С#, связанной с выше.

Синтаксический

Большинство парсеров известны как партизаны смены-сдвига. Это означает, что токены перемещаются в стек поэтапно и уменьшаются (удаляются), когда они соответствуют правилу. Чтобы помочь совпадение, синтаксический анализатор будет иметь определенное количество контрольных токенов, которые он может наблюдать (я считаю, что это наиболее часто встречающийся). В общем, успешный анализ завершится, когда все токены будут уменьшены.

Тип анализатора, который реализуется программами построения компилятора, такими как YACC и GPPG известен как парсер LALR(1). Эти работы путем создания таблицы синтаксического анализа, основанной на каждой юридической комбинации состояния синтаксического анализатора и символа вида, и учитывая текущее состояние и следующий символ, могут затем рассказать нам, как вычислить следующее состояние.

Теперь, когда у нас есть наши жетоны, мы запускаем их в парсер, результатом которого обычно будет абстрактное синтаксическое дерево , которое может можно использовать для последующих задач, таких как генерация кода, проверка семантического типа и т.д. Для анализа этих токенов нам нужны правила, чтобы сгруппировать их в значимые синтаксические единицы - это то, что предотвращает путаницу при встрече >>.

Из грамматики С#:

declaration_statement:
    | local_variable_declaration ";" 
    | local_constant_declaration ";" 

local_variable_declaration:
    | local_variable_type local_variable_declarators 

local_variable_type:
    | type 
    | "var"

local_variable_declarators:
    | local_variable_declarator 
    | local_variable_declarators "," local_variable_declarator 

local_variable_declarator:
    | identifier 
    | identifier "=" local_variable_initializer 

type:
    | value_type 
    | reference_type 
    | type_parameter 
    | type_unsafe 

value_type:
    | struct_type 
    | enum_type 

struct_type:
    | type_name 
    | simple_type 
    | nullable_type 

simple_type:
    | numeric_type 
    | bool 

numeric_type:
    | integral_type 
    | floating_point_type 
    | decimal 

integral_type:
    | "sbyte" 
    | "byte" 
    | "short" 
    | "ushort" 
    | "int"
    | "uint" 
    | "long"
    | "ulong" 
    | "char"

reference_type:
    | class_type 
    | interface_type 
    | array_type 
    | delegate_type 

class_type:
    | type_name 
    | "object"
    | "dynamic" 
    | "string"

type_name:
    | namespace_or_type_name 

namespace_or_type_name:
    | identifier type_argument_list? 
    | namespace_or_type_name "." identifier type_argument_list? 
    | qualified_alias_member 

identifier:
    | available_identifier 
    | "@" identifier_or_keyword 

type_argument_list:
    | "<" type_arguments ">" 

type_arguments:
    | type_argument 
    | type_arguments "," type_argument 

type_argument:
    | type 

Сложно выглядит, но оставайся со мной. Каждое правило имеет вид

rule_name:
    | production_1
    | production_2
    | production_2

Каждое производство может быть другим правилом (не терминал) или терминалом. Возьмите правило integral_type, например: все его производные являются терминалами. Правила также могут ссылаться на самих себя, так как рассматриваются такие вещи, как аргументы типа в Tuple<int, int, double>.

В этом примере я предполагаю, что List<Nullable<int>> list; является объявлением локальной переменной. Вы можете найти более простой пример на странице Shift-Reduce Parsing на странице Википедии, а другой на LR Parsing.

Начнем с того, что наш Parse Stack пуст, наш единственный лексанный токен - это первый, и нашим первым действием будет переход этого токена. То есть наше парсерное состояние будет выглядеть так:

Step 0
Parse Stack:    empty
Look Ahead:     available_identifier
Unscanned:      List<Nullable<int>> list;
Parser Action:  Shift

В нашем следующем шаге мы можем уменьшить текущий токен на основе производственного identifier <- available_identifier.

Step 1
Parse Stack:    available_identifier
Look Ahead:     "<"
Unscanned:      <Nullable<int>> list;
Parser Action:  Reduce by identifier <- available_identifier

Пропустив несколько шагов, на шаге 10 мы получим следующее состояние парсера:

Step 10
Parse Stack:    identifier "<" identifier "<" type_arguments ">"
Look Ahead:     ">"
Unscanned:      > list;
Parser Action:  Reduce by type_argument_list <- "<" type_arguments ">"

В этот момент мы сможем сократить последние три токена, поскольку их последовательность составляет type_argument_list (это можно проверить в приведенных выше правилах). Ускорьте вперед немного дальше к шагу 13, и у нас есть следующее:

Step 13
Parse Stack:    identifier "<" type_arguments ">"
Look Ahead:     ">"
Unscanned:      list;
Parser Action:  Reduce by type_argument_list <- "<" type_arguments ">"

Как и на шаге 10, мы уменьшаем на type_argument_list <- "<" type_arguments ">". При этом мы фактически избегали какой-либо двусмысленности с помощью >>. Эти шаги продолжаются до тех пор, пока мы не уменьшим на declaration_statement <- local_variable_declaration ";" - первое правило выше.

Резюме

Создавая недвусмысленную грамматику, синтаксические анализаторы могут легко рассортировать, казалось бы, сложные ситуации, такие как List<Nullable<int>>. То, что я здесь рассмотрел, по существу, является парсером LALR (1) снизу вверх. Я не занимался фактическим созданием абстрактного синтаксического дерева, но вы, вероятно, достаточно на своей тарелке с указанным выше.

Имейте в виду, что правила не включали начальное состояние - это было главным образом ради краткости. Если это полезно, я могу оставить остальные шаги анализа.

Изменить: f(g<a, b>(c))

В этой грамматике должно быть два правила invocation_expression, которые имеют вид invocation_expression -> primary_expression ( argument_list? )

Первый соответствует g<a, b>(c). Он делает это, сначала устанавливая, что g<a,b> является identifier, за которым следует type_argument_list. Наш взгляд теперь "(", и потому, что анализатор будет знать из предыдущего контекста, что этот код находится в теле метода, он может уменьшить identifier type_argument_list на

primary_expression <- primary_no_array_creation_expression
    <- simple_name <- identifier type_argument_list?

После сдвига "(" и c мы можем уменьшить c на

argument_list <- argument <- argument_value <- expression
    <- <a really long list of rules> <- simple_name
    <- identifier <- available_identifier

И перевод этого конечного символа в скобки дает нам

primary_expression ( argument_list? )

который затем может быть уменьшен правилом invocation_expression, таким образом, сопоставляя g<a, b>(c).

К этому моменту мы бы уже сопоставили f как identifier и применили редукцию

primary_expression <- primary_no_array_creation_expression
    <- simple_name <- identifier type_argument_list?

Таким образом, стек синтаксического анализа будет содержать следующие

primary_expression "(" invocation_expression
        ^           ^            ^
        f           (        g<a, b>(c)

Символ с просмотром будет самым последним ")", поэтому синтаксический анализатор уменьшит invocation_expression на

argument_list <- argument <- argument_value <- expression
    <- <the same really long list of rules> <- primary_expression
    <- primary_no_array_creation_expression <- invocation_expression

Смена последнего ")" даст нам

    primary_expression "(" argument_list ")"
            ^           ^        ^        ^
            f           (    g<a, b>(c)   )

Как и раньше, это можно уменьшить с помощью правила invocation_expression, таким образом сопоставив f(g<a, b>(c)).

Ответ 2

Вы можете отложить решение до тех пор, пока не закончите синтаксический анализ и/или семантический анализ (компиляторы AFAIK C/С++ должны использовать последний подход).

Я написал статью, как вы можете сделать это с помощью парсера (NLT в этом случае), которые позволяют параллельно анализировать ваш ввод с разными интерпретациями - Неоднозначность? Пусть NLT проанализирует его для вас. Короче говоря, вы не решаете, является ли это скользящим или скользящим угловым скобком для общего аргумента, вы в порядке с обеими версиями, однако вы ждете, пока один из них не окажется недействительным, тогда вы его убьете, и вы получите правильный.

Я не вставляю здесь полный текст, потому что слишком долго для ответа SO.

Ответ 3

Я спросил тот же вопрос о Java.

В основном проблема заключается в том, что:

• язык недвусмыслен (по крайней мере, в этом примере) - это означает, что существует только один правильный способ его анализа.
• некоторые реализации будут неоднозначно обозначать этот пример - это означает, что существует более одного способа разделить входные данные на действительные токены

• в зависимости от контекста, для правильного разбора требуется различная токенизация - сравните:

  A<B<C >> d = new A<B<C >> ();
  
  E >> f;
  

Я хотел бы подчеркнуть, что проблема не вызвана самим языком, а некоторыми подходами к его анализу. В зависимости от того, как/что вы используете для его анализа, вы можете вообще не испытывать эту проблему.

Однако, если вы столкнулись с этой проблемой, вот несколько общих решений:

• дать токенизатору достаточную информацию о том, что контекст корректно обозначается. Например, разрешите токенизацию быть контекстно-зависимой, а не регулярной, возможно, интегрируя токенизацию с иерархическим разбором. В конце концов, отдельный проход для токенизации является просто детальностью реализации для эффективности, а не необходимой частью синтаксического анализа. Этот подход довольно легко реализовать с помощью парсеров с рекурсивным спусками.

• неоднозначно марксировать и разрешать двусмысленности, когда доступна более контекстная информация. (Это может показаться неэффективным в теории, но на практике есть очень быстрые реализации.)

• делать наивные токенизации, но при необходимости переинтерпретировать токены. Это решение, по-видимому, используется некоторыми парсерами языка Java, как более подробно объяснено в моем аналогичном вопросе.