Wiki**3

The Problem (in Portuguese)

Pretende-se calcular o nível de complexidade de uma mensagem (nível de aninhamento de mensagens). As mensagens são delimitadas por { e por }: o conteúdo entre os delimitadores é uma sequência de elementos, sendo o primeiro necessariamente um símbolo (uma letra seguida, possivelmente, por letras ou algarismos decimais). Os restantes elementos podem ser: (i) símbolos; (ii) números inteiros decimais; (iii) outras mensagens (embebidas); (iv) cadeias de caracteres (entre plicas ', mas, por simplicidade, não contendo plicas) (v) listas. As listas começam com ( e terminam com ). Dentro de listas podem ocorrer elementos atómicos como os anteriores e outras listas, mas não mensagens. Não há restrições à posição de elementos numa lista. As listas numa mensagem, para efeitos de aninhamento, são contabilizadas como se fossem elementos atómicos.

Os vários elementos de uma mensagem são separados por espaços brancos, tabulações (\t) ou mudanças de linha (\n). Um comentário é iniciado por ; e termina no fim da linha (podem ser inseridos onde é esperado um separador).

Note-se que alguns caracteres nem sempre têm o mesmo significado.

Exemplos:

{m1 '{f();}' (1 2 3) 1} ; complexidade 1
{m2 123 {m1 '{f();}' ('1' '2' '3') 1}} ; complexidade 2
{m3 (1 2 (3 4 ((5) 6))) {m1 ';;e=mc^2;;' {m2 '{f();}' ((1 b d) 1)} 123}} ; complexidade 3

Apresente a especificação de um analisador lexical (para a ferramenta Flex) que resolva o problema indicado (todas as funções auxiliares devem ser implementadas).

The Solution

Assuming a single message:

%option stack 8bit noyywrap yylineno
%{
#include <iostream>
namespace {
  // module-private variables
  int current = 0;
  int complexity = 0;
}
void yyerror(const char *msg);
%}
%x xMESSAGE xLIST xSTRING
%%

"{"             yy_push_state(xMESSAGE); current++;
<xMESSAGE>"{"   yy_push_state(xMESSAGE); current++;
<xMESSAGE>"}"   yy_pop_state(); complexity = current > complexity ? current : complexity; current--;
<xMESSAGE>"("   yy_push_state(xLIST);
<xMESSAGE>"'"   yy_push_state(xSTRING);
<xMESSAGE>";".* ; // ignore comments in messages
<xMESSAGE>.|\n  ; // ignore the rest

<xLIST>"("      yy_push_state(xLIST);
<xLIST>"'"      yy_push_state(xSTRING);
<xLIST>")"      yy_pop_state();
<xLIST>";".*    ; // ignore comments in lists
<xLIST>.|\n     ; // ignore the rest

<xSTRING>"'"    yy_pop_state();
<xSTRING>.      ; // ignore the rest
<xSTRING>\n     yyerror("newline in string");

";".*$          ; // ignore comments
.|\n            ; // ignore the rest

%%
void yyerror(const char *msg) { std::cerr << msg << std::endl; }
int main() {
  yylex();
  std::cout << "Complexity: " << complexity << std::endl;
}