Как Flex различает A, AB и ABC?

Question

Я сделал этот эксперимент для Flex, чтобы узнать, вхожу ли я в ABC, если он увидит все A, AB, ABC или только ABC или только первое совпадение в списке выражений.

%{ 
#include <stdio.h> 
%} 

%% 
A puts("got A"); 
AB puts("got AB"); 
ABC puts("got ABC"); 
%% 

int main(int argc, char **argv) 
{ 
    yylex(); 

    return 0; 
} 

Когда я вхожу ABC после компиляции и запуска программы, она отвечает «Got ABC», который действительно удивляет меня, так как я думал, что закон не следить за посещаемый текст, и находит только первый матч; но на самом деле это похоже на самый длинный матч.

Какую стратегию использует Flex для ответа на A тогда и только тогда, когда ее больше нет?

Answer 1

Тот факт, что (F) закон использует принцип maximal-munch вряд ли стоит удивляться, так как хорошо документированы в Flex manual:

Когда генерируется сканер запускается, он анализирует входные данные ищет строки, которые соответствуют любому из его шаблонов. Если он находит более одного совпадения, он принимает тот, который соответствует самому тексту & hellip ;. Если он находит два или более совпадений одинаковой длины, выбирается правило, указанное первым в файле ввода flex. (первый абзац раздела «Как вход согласованного»)

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

Следствием является то, что (F) lex может сканировать один и тот же текст несколько раз, хотя он сканирует только один раз для каждого токена.

Набор лексических правил, требующих чрезмерного отслеживания назад, замедлит лексическое сканирование. Это обсуждается в разделе руководства Flex Performance Considerations, а также некоторые стратегии, позволяющие избежать проблемы. Однако, за исключением патологических случаев, накладные расходы от отслеживания назад не являются заметными.