Есть ли лучший способ указать дополнительные элементы в правилах CFG?

Question

Рассмотрите язык и компилятор для его разработки и разработки. На этом языке есть определенное утверждение, которое является частью грамматики: (=<identifier>). Этот кусок может быть распознан компилятором. Но между скобками и знаком равенства и идентификатором допускаются пробелы. Таким образом, у меня есть эти возможности:

(=<identifier>) 
(= <identifier>) 
(=identifier) 
(=identifier) 
... 

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

statement: OBRCKT EQ ID CBRCKT 
     | OBRCKT S EQ S ID S CBRCKT 
     | OBRCKT S EQ ID S CBRCKT 
     | OBRCKT S EQ S ID CBRCKT 
     | OBRCKT S EQ ID CBRCKT 
     | OBRCKT EQ S ID S CBRCKT 
     | OBRCKT EQ ID S CBRCKT 
     | OBRCKT EQ S ID CBRCKT 
     | ... 

Космический терминал S может отображаться или нет. Но, как правила, я должен указать все возможные комбинации ... Есть ли лучший способ достичь этого результата?

Answer 1

Как прокомментировал Джим, используйте свой лексический инструмент для обработки этих случаев вместо того, чтобы записывать их в произведения вашей грамматики.

Например, я обычно использую Flex для лексического анализа и Bison для определения моей грамматики (возможно, как вы это сделали).

Вы можете достичь результата, который вы хотите что-то вроде следующего (это просто пример, так что это очень просто и не делать):

lexicalAnalyzer.l

/* lexicalAnalyzer.l 
    Specifications of tokens for some language. 
*/ 
%{ 

%} 

/* 
* Definitions of regular expressions 
* Note: You capture whitespace here... 
*/ 

WSPACE  [ \t\r]+ //We take care of the spaces here... 

/* 
* Tokens 
*/ 
%% 

"=" { 
     printf("TOKEN: EQ LEXEME: %s\n", yytext);    
     return T_EQ; 
    } 
"(" { 
     printf("TOKEN: OBRCKT LEXEME: %s\n", yytext); 
     return T_OBRCKT; 
    } 
")" { 
     printf("TOKEN: CBRCKT LEXEME: %s\n", yytext); 
     return T_CBRCKT; 
    } 
"<" { 
     printf("TOKEN: LT LEXEME: %s\n", yytext); 
     return T_LT; 
    } 
">" { 
     printf("TOKEN: GT LEXEME: %s\n", yytext); 
     return T_GT; 
    } 
"identifier" { 
       printf("TOKEN: IDENT LEXEME: %s\n", yytext); 
      return T_IDENT; 
      } 
{WSPACE} { } 
.  { 
       printf("TOKEN: UNKNOWN LEXEME: %s\n", yytext); 
       return T_UNKNOWN; 
      } 
%% 

syntaxAnalyzer.y

/* 
     syntaxAnalyzer.y 

     To create syntax analyzer: 
     flex file.l 
     bison file.y 
     g++ file.tab.c -o file_parser 
     file_parser < inputFileName 
*/ 

/* 
* Declaration section. 
*/ 

%{ 

    #include <stdio.h> 
    void printRule(const char *lhs, const char *rhs); 
    int yyerror(const char *s) { 
     printf("Error!"); 
    } 
    extern "C" { 
     int yyparse(void); 
     int yylex(void); 
     int yywrap() {return 1;} 
    } 
%} 

/* 
* Token declarations 
*/ 
%token T_OBRCKT T_CBRCKT 
%token T_LT T_GT T_EQ 
%token T_IDENT T_UNKNOWN 

/* 
* Starting point. 
*/ 
%start N_START 

/* 
* Translation rules. 
*/ 
%% 
N_START  : N_STATEMENT 
      { 
       printRule("START", "STATEMENT"); 
       printf("\n---- Completed parsing ----\n\n"); 
       return 0; 
      } 
      ; 

N_STATEMENT : T_OBRCKT T_EQ T_LT T_IDENT T_GT T_CBRCKT 
      { 
      printRule("EXPR", "T_OBRCKT T_EQ T_LT T_IDENT T_GT T_CBRCKT"); 

      } 
      ; 
%% 

#include "lex.yy.c" 
extern FILE *yyin; 

void printRule(const char *lhs, const char *rhs) { 
    printf("%s -> %s\n", lhs, rhs); 
    return; 
} 

int main() { 
    do { 
    yyparse(); 
    } while (!feof(yyin)); 
    return 0; 
}