Использование Flex и Bison?

Question

Работа над заданием, которое требует использования flex и bison для проверки наличия данной строки на языке. Это происходит только после того, как мы увидели основные примеры, когда flex использовался, чтобы в основном переплеть то, что было прочитано.

Например, строка в формате {a^nb^nc^n} с n> 0 будет находиться в язык. Таким образом, строка aabbcc будет действительна.

Есть ли способ для гибкого подсчета конкретных символов? Например, если строка aaabbbcc, если дана, она будет считать 3 a, 3 b и 3 c? Или мне просто нужно использовать flex, чтобы проверить, что входная строка просто в правильном формате, а затем использовать правила грамматики в бизоне, чтобы проверить, есть ли это на языке?

EDIT
Я работал над ним некоторое время и, кажется, имеют рабочую версию полу. Проблемы, с которыми я сталкиваюсь сейчас, это то, что yyparse() никогда не выходит, и когда указана некорректная строка, она встречает синтаксическую ошибку. Например:
Строка «aabbcc» должна быть в том, что я называю L2. Я получу следующий результат:

grammar recognizer result: 
L2 recognized 

Затем он просто останавливается и никогда не заканчивается. Кроме того, строка «hjnkll» не должна распознаваться, но я получаю синтаксическую ошибку при вводе чего-то подобного.
Flex

... 
A [a]* 
B [b]* 
C [c]* 
D [d]* 
E [e]* 
Z [^a-e\n][.]* 
%% 
{A} {a = yyleng;} return A; 
{B} {b = yyleng;} return B; 
{C} {c = yyleng;} return C; 
{D} {d = yyleng;} return D; 
{E} {e = yyleng;} return E; 
{Z} {z = yyleng;} return Z; 
\n return NL; 
%% 

Bison Snipets

%token A 
%token B 
%token C 
%token D 
%token E 
%token Z 
%token NL 

%% 
/*grammer rules*/ 
transunit: L1 | L2 | L5 | L6 
    { 
    printf("\n*****Congratulations; Parse Successful*****\n"); 
    } 
; 
L2: A B C NL 
    { 
    /*Language 2 : L(G2) = {a^nb^nc^n} with n > 0*/ 
    if(a==b && b==c && d==0 && e==0 && a!=0 && z==0){ 
     printf("\nLG2 recognized\n"); 
    } else { 
     printf("\nSorry language not recognized\n"); 
    } 
    } 
; 
/*None of the above : not recognized*/ 
L6: Z NL 
    { 
    printf("\nSorry language not recognized\n"); 
    } 
; 

Answer 1

Строка ^п б ^п с ^п не является ни регулярными, ни контекст бесплатно. Строка может генерироваться только Context Sensitive Grammar или Unrestricted Grammar в зависимости от значения n. Поэтому строка не может быть проверена с использованием Flex или Bison. Flex - это генератор сканера, и он может проверять только регулярные выражения. Bison - генератор синтаксического анализатора, и он может проверять только контекстно-зависимые языки.

Answer 2

Для вашего конкретного примера вы можете совместить a+b+c+ с использованием состояний. Затем просто проверьте количество вхождений a, b и c и убедитесь, что все они равны. Однако это решение быстро растет экспоненциально сложным, если ваш язык имеет более 2 или 3 правил.

%{ 
int a = 0, b = 0, c = 0; 
%} 
%x Bstate Cstate 
%% 
"a"+    { a = yyleng; BEGIN(Bstate);   } 
.     { /* not in language; error! */  } 
<Bstate>"b"+  { b = yyleng; BEGIN(Cstate);   } 
<Bstate>.   { /* not in language; error! */  } 
<Cstate>"c"+  { c = yyleng; 
         if(a != b || a != c) { 
          /* not in language; error! */ 
         } 
         BEGIN(INITIAL);      } 
<Cstate>.   { /* not in language; error! */  } 
%% 

С другой стороны, вы могли бы просто сказать сгибать, чтобы соответствовать "a"+"b"+"c"+ затем итерации по характеру строки по характеру, но это делает использование гибкого излишним.

Смотрите здесь для получения дополнительной информации о состояниях: http://aquamentus.com/flex_bison.html#17 `

Answer 3

Просто для полноты картины, просто добавить подсчет чеки зубров. Вот простой пример (который распознает или жалуется на вводные строки, чтобы облегчить игру):

Я упустил большинство деталей шаблонов, включая функцию и yyerror. Но я сделал некоторые варианты гибкой работы.Использование 'a' означает, что «любое число a s» растягивает границы; было бы лучше иметь определенные жетоны, которые назывались As, Bs и Cs, а затем разделили правила гибки на пять разных правил и т. д. и т. д. Это было короче. :)

зубр

%{ 
#include <stdio.h> 
%} 
%% 
start: line 
    | start line 
    ; 

line: 'a' 'b' 'c' '\n' { if ($1 == $2 && $2 == $3) 
          fputs("Good!\n", stderr); 
         else 
          fputs("Bad!\n", stderr); 
         } 

прогибается:

%{ 
extern int yylval; 
%} 
%option noyywrap noinput nounput  
%% 
"a"+|"b"+|"c"+|.|\n { yylval = yyleng; return *yytext; }