flex e expressões regulares

  • Published on
    05-Aug-2015

  • View
    89

  • Download
    4

Embed Size (px)

Transcript

<p>Licenciatura em Engenharia Informtica DEI/ISEP Linguagens de Programao 2006/07</p> <p>Ficha</p> <p>1</p> <p>Introduo ao FLEX e expresses regulares</p> <p>Objectivos: Familiarizao com a ferramenta FLEX; Introduo ao reconhecimento de padres e expresses regulares; Aprendizagem dos conceitos atravs da realizao de alguns exerccios; Apresentar o ambiente de trabalho proposto (seco 1.6); Relembrar alguns comandos bsicos de Linux importantes para a utilizao do FLEX (seco 1.7).</p> <p>1.1</p> <p>Analisadores lxicos</p> <p>Um analisador lxico (scanner ) um programa que permite ler os caracteres de um cheiro de texto (e.g., programa-fonte) e produzir uma sequncia de componentes lxicos (tokens) que sero utilizados pelo analisador sintctico (parser ) e/ou identicar erros lxicos na entrada. Alm de sua funo bsica, o analisador lxico em geral est encarregue de fazer algumas tarefas secundrias, designadamente, a eliminao de comentrios, espaos em branco e tabulaes. Um token representa um conjunto de cadeias de entrada possvel e por sua vez, um lexema uma determinada cadeia de entrada associada a um token. Considere os exemplos apresentados na tabela 1.1. O FLEX uma ferramenta que permite gerar analisadores lxicos. Estes analisadores so capazes de reconhecer padres lxicos em texto (e.g., nmeros, identicadores e palavras-chave de uma determinada linguagem de programao). O analisador construdo com base num conjunto de regras. Uma regra constituda por um par, padroaco, o padro (expresso regular) descreve o elemento a reconhecer e aco (ou conjunto de aces) dene o procedimento que ser realizado no caso de identicao positiva do padro.</p> <p>1</p> <p>Tabela 1.1: Tokens e lexemas Tokens Lexemas FOR for IF if WHILE while NMERO 1089, 142857, 0.2, 3.14159 IDENTIFICADOR i, j, contador, nomeAluno OP_SOMA + OP_MAIOR_IGUAL &gt;= ABRE_PAR (</p> <p>1.2</p> <p>Modo de utilizao do FLEX</p> <p>O ciclo de vida de um programa FLEX obedece estrutura apresentada na gura 1.1.Erros de FLEX Erros de compilaoFicheiro texto n Ficheiro texto 2 Ficheiro texto 1</p> <p>ficheiro fonte flex .flex</p> <p>FLEX</p> <p>ficheiro fonte C .c</p> <p>Compilador (gcc)</p> <p>programa executvel</p> <p>Resultado 2 Resultado 1</p> <p>Resultado n</p> <p>Figura 1.1: Ciclo de vida de um programa FLEXCom base num cheiro fonte escrito de acordo com a sintaxe do FLEX, o programa FLEX gerar um analisador lxico descrito na linguagem C. Em caso de existirem erros de codicao, o FLEX gerar uma listagem de erros. O cheiro fonte em C ter de ser compilado para a plataforma em utilizao utilizando um compilador da linguagem C adequado (neste caso o GCC). O resultado nal da compilao ser um programa executvel capaz de identicar os padres denidos pelo programado e levar o conjunto de aces previsto. Como entrada para o analisador gerado podem ser fornecidos cheiros de texto ou alternativamente fornecer os dados directamente pelo standard de entrada. No exemplo seguinte so apresentados os passos necessrios compilao e utilizao de um programa FLEX. Considere-se a existncia de um cheiro ficheiro.flex</p> <p>2</p> <p>com o programa FLEX j escrito. flex ficheiro.flex gcc lex.yy.c -lfl ./a.out O comando flex gera, por omisso, um cheiro com o nome lex.yy.c que dever ser compilado, por exemplo com o gcc. Na utilizao do gcc necessrio indicar a utilizao da biblioteca FLEX adicionando o parmetro -lfl. Por sua vez, o compilador de C gera, por omisso, um cheiro com o nome a.out. Por ltimo, para a execuo deste programa basta a evocao do seu nome na linha de comandos. Neste caso, a introduo dos dados ter de ser realizada via consola (terminando obrigatoriamente com Ctrl+D). flex -oExemplo.c Exemplo.flex gcc Exemplo.c -o Programa -lfl ./Programa &lt; Dados.txt Neste exemplo, o comando flex gera a partir do cheiro Exemplo.flex, o cheiro com o nome Exemplo.c que dever ser compilado. Nesta utilizao apresentada do gcc, indicado o nome do executvel a ser gerado, neste caso, Programa. Na execuo do Programa, a introduo dos dados realizada a partir do cheiro Dados.txt.</p> <p>1.3</p> <p>Formato de um cheiro FLEX</p> <p>Um programa em FLEX constitudo por trs seces, a saber, declaraes, regras e rotinas auxiliares. A separao entre as seces feita inserindo uma linha com o smbolo %%. Considere-se o seguinte exemplo que ser discutido nas seces seguintes.1 2 3 4 5 6 7 8 9 10 11 12</p> <p>%{ int numChars=0; %} %% . { numChars++; p r i n t f ( "%s " , y y t e x t ) ; } \n {</p> <p>3</p> <p>13 14 15 16 17 18 19 20 21 22 23 24</p> <p>numChars++; p r i n t f ( "\n" ) ; } %% main ( ) { yylex ( ) ; p r i n t f ( "Nmero de c a r a c t e r e s %d\n" , numChars ) ; }</p> <p>1.3.1</p> <p>Declaraes</p> <p>Esta seco compreende duas partes: Instrues C nesta parte, delimitada pelos smbolos %{ e %}, so colocadas as instrues da linguagem C que posteriormente sero includas no incio do cheiro C a gerar pelo FLEX. Os exemplos mais comuns so a incluso de cheiros de cabealhos ( headers, .h), declaraes de variveis e constantes.1 2 3 4</p> <p>/ D e f i n i o da v a r i v e l numChars / %{ int numChars=0; %}</p> <p> Expresses regulares nesta parte, podem ser declaradas macros para as expresses regulares mais comuns como por exemplo algarismo ou letra do alfabeto.1 2 3</p> <p>/ D e f i n i o de macros / ALGARISMO [0 9] / Algarismo / ALFA [ azAZ ] / L e t r a do a l f a b e t o / A utilizao de macros para expresses regulares ser explicada com detalhe mais adiante.</p> <p>1.3.2</p> <p>Regras (denio de padres e aces)</p> <p>Nesta seco so denidas as expresses regulares (padres) e as respectivas aces que se pretendem realizar no caso da identicao positiva (pattern matching) do referido padro.</p> <p>4</p> <p>No caso de um qualquer carcter excepto mudana de linha (representado por .) incrementada a varivel num_chars e impresso o referido carcter no standard de sada. A mudana de linha (representado por \n) tambm contabilizada como um carcter e escrita no standard de sada. As expresses regulares tm de ser obrigatoriamente escritas na primeira coluna do cheiro.1 2 3 4 5 6 7 8 9</p> <p>.</p> <p>{ numChars++; p r i n t f ( "%s " , y y t e x t ) ; }</p> <p>\n</p> <p>{ numChars++; p r i n t f ( "\n" ) ; }</p> <p>Na seco 1.8 so apresentados alguns dos padres mais relevantes utilizados pelo FLEX. o analisador lxico gerado funciona de acordo com as seguintes regras: Apenas uma regra aplicada entrada de dados; A aco executada corresponde expresso que consome o maior nmero de caracteres; Caso existam duas ou mais expresses que consumam igual nmero de caracteres, tem precedncia a regra que aparece em primeiro no cheiro. Quando um padro reconhecido, a sequncia de caracteres consumida (token) na identicao do padro guardada na varivel yytext (do tipo char *). Para alm disso, o comprimento da referida sequncia guardado na varivel yyleng1 (do tipo int).</p> <p>1.3.3</p> <p>Rotinas em C de suporte</p> <p>Nesta seco pode ser escrito o cdigo C que se pretende que seja adicionado ao programa a gerar pelo FLEX. Tipicamente este cdigo inclui o corpo do programa, designadamente, a funo main() da linguagem C.1 2 3 4 5</p> <p>main ( ) { yylex ( ) ; p r i n t f ( "Nmero de c a r a c t e r e s %d\n" , numChars ) ; }O valor desta varivel poderia ser obtido atravs da instruo da linguagem C strlen(yytext)1</p> <p>5</p> <p>A funo yylex() evoca o analisador lxico gerado pelo ex que processar as expresses regulares anteriormente descritas (ver seco 1.3.2).</p> <p>1.4</p> <p>Exemplo mais elaborado</p> <p>Considere o seguinte exemplo, no qual contabilizado a quantidade de nmeros e de linhas existentes no cheiro. Neste exemplo recorre-se utilizao de uma macro para a denio de algarismo.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22</p> <p>%{ int qtdNumeros =0, nLinhas =0; %} ALGARISMO %% / Se a aco f o r d e s c r i t a numa s l i n h a as c h a v e t a s podem s e r o m i t i d a s / \n {ALGARISMO}+ . nLinhas++; { p r i n t f ( "d %s \n" , y y t e x t ) ; qtdNumeros++;} [0 9]</p> <p>%% main ( ) { yylex ( ) ; p r i n t f ( "# l i n h a s=%d\n" , nLinhas ) ; p r i n t f ( "# numeros=%d\n" , qtdNumeros ) ; } Todos os caracteres no processados pelas duas primeiras expresses regulares so consumidos pela ltima qual no corresponde nenhuma aco particular.</p> <p>1.5</p> <p>Propostas de exerccios</p> <p>a) Escrever um programa que permite contar o nmero de ocorrncias de uma cadeia de caracteres; b) Escrever um programa que permite substituir uma cadeia de caracteres por outra;</p> <p>6</p> <p>c) Escrever um programa que dado um cheiro de texto, mostra: nmero de algarismos; nmero de letras do alfabeto; nmero de linhas de texto; nmero de espaos ou tabulaes (\t); nmero de caracteres no identicados nos pontos anteriores; d) Escrever um programa que permite identicar nmeros naturais;</p> <p>Entrada 123 abc 12.45 s 245 xyz xyz 2 abc 45 cc</p> <p>Sada 123 12 45 245 2 45</p> <p>e) Escrever um programa que permite identicar nmeros inteiros (com ou sem sinal); f) Escrever um programa que permite identicar nmeros com parte decimal (com ou sem sinal);</p> <p>7</p> <p>1.6</p> <p>Ambiente de trabalho</p> <p>O acesso a uma mquina LINUX pode ser realizado utilizando o programa putty que est instalado em c:putty em modo SSH (ver gura 1.2). As mquinas a utilizar devero ser ssh, ssh1 e ssh2.</p> <p>Figura 1.2: Acesso SSH via puttyA edio dos cheiros fonte pode ser realizada a partir de qualquer editor de texto bsico (e.g., no ambiente Windows existe o Programmers Notepad) desde que os cheiros sejam gravados em formato Unix.</p> <p>1.7</p> <p>Resumo de comandos UNIX teis</p> <p>Na tabela 1.2 so apresentados os comandos que permitem fazer mudana de directrio e mostrar qual o directrio actual.</p> <p>Comando cd cd .. cd pwd</p> <p>Tabela 1.2: Mudar e mostrar directrio Descrio Mudar para o directrio home Mudar para o directrio pai Mudar para o directrio DIR Mostra o path do directrio actual 8</p> <p>Na tabela 1.3 so apresentados os comandos que permitem listar o contedo de um determinado directrio.</p> <p>Tabela 1.3: Listagem do contedo de um directrio Comando Descrio ls Mostra contedo do directrio actual ls -a idem incluindo cheiros escondidos ls -la idem incluindo cheiros escondidos sob a forma de lista ls -l Mostra contedo do directrio DIR sob a forma de listaNa tabela 1.4 so apresentados os comandos que permitem alterar as permisses de acesso a cheiros e/ou directrios. As permisses podem ser de trs tipos: Leitura (r) permite visualizar o contedo quando de se trate de cheiros, no caso de directrios, permite fazer um ls; Escrita (w) permite alterar o contedo quando de se trate de cheiros e no caso de directrios permite criar cheiros/directrios no referido directrio; Execuo (x) permite executar um programa, quando de se trate de cheiros, no caso de directrios, permite aceder aos seus contedos; As permisses de acesso a um cheiro ou directrio esto subdivididas por trs grupos de utilizadores: o prprio (owner ); o grupo (group); restantes (other ). Considere o seguinte extracto resultado da execuo do comando ls -la no qual o primeiro campo faz a codicao das permisses leitura, escrita e execuo (rwx) para cada grupo. Estas permisses podem ser convertidas para um valor numrico somando 4 para r, 2 para w e 1 para x. -rwxr----drwx--x--1 user 4 user profs profs 25 Jan 27 2002 fich 4096 Jan 17 16:31 dir/</p> <p>Neste exemplo, o cheiro fich tem permisses de leitura, escrita e execuo para o prprio, leitura para o grupo e nenhuma para os restantes utilizadores. Por sua vez, o directrio dir (o primeiro carcter um d no caso de directrios) tem permisses de leitura, escrita e execuo para o prprio, execuo para o grupo e nenhuma para os restantes utilizadores.</p> <p>9</p> <p>Tabela 1.4: Alterao de permisses de acesso de cheiros/directrios Comando Descrio chmod u+rwx,go-rw Concede as permisses rwx para o utilizador; retira as permisses rw para utilizadores do mesmo grupo e outros; as outras permisses no so alteradas chmod u+rwx,go+rx Concede as permisses rwx para o utilizador; concede as permisses rx para utilizadores do mesmo grupo e outros; as outras permisses no so alteradas chmod 751 Concede somente as permisses: rwx (7 = 4 + 2 + 1) para o utilizador, rx (5 = 4 + 1) para utilizadores do mesmo grupo e x (1) para outros utilizadores</p> <p>1.8</p> <p>Padres utilizados no FLEX</p> <p>Na tabela 1.5 so apresentados alguns dos padres mais relevantes utilizados pelo FLEX. Tabela 1.5: Padres utilizados no FLEX Padro x . \n [xyz] xyz [a-zA-Z] [-+*/] Descrio O carcter x Qualquer carcter excepto mudana de linha Mudana de linha Um dos caracteres x, y ou z A cadeia de caracteres xyz Um dos caracteres no intervalo de a a z ou de A a Z Qualquer um dos operadores -, +, * ou /, send que o smbolo - tem de aparecer em primeiro lugar dada a possibilidade de ambiguidade com a denio de intervalo Um dos caracteres a, b ou de j a o ou Z Qualquer carcter excepto no intervalo de A a Z ou mudana de linha O carcter r zero ou mais vezes O carcter r uma ou mais vezes O carcter r zero ou uma vez O carcter r repetido de duas a cinco vezes O carcter r repetido pelo menos duas vezes O carcter r repetido exactamente quatro vezes</p> <p>[abj-oZ] [A-Z\n] r* r+ r? r{2,5} r{2,} r{4}</p> <p>10</p> <p>Tabela 1.5: Padres utilizados no FLEX Padro {macro} (r) xyz* (xyz)* r|s r r$ xyz$ Descrio Substituio/Expanso da macro denida anteriormente O carcter r, sendo que os parntesis permitem estipular precedncias A sequncia xy seguida de zero ou mais zs A sequncia xyz repetida zero ou mais vezes O carcter r ou s (alternativa) O carcter r apenas se no incio da linha O carcter r apenas se no nal da linha (no consome o \n) Uma linha que contm apenas a cadeia de caracteres xyz Fim de cheiro</p> <p>11</p>

Recommended

View more >