flex e expressões regulares

  • Published on
    05-Aug-2015

  • View
    89

  • Download
    4

Embed Size (px)

Transcript

Licenciatura em Engenharia Informtica DEI/ISEP Linguagens de Programao 2006/07

Ficha

1

Introduo ao FLEX e expresses regulares

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).

1.1

Analisadores lxicos

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.

1

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 >= ABRE_PAR (

1.2

Modo de utilizao do FLEX

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

ficheiro fonte flex .flex

FLEX

ficheiro fonte C .c

Compilador (gcc)

programa executvel

Resultado 2 Resultado 1

Resultado n

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

2

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 < 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.

1.3

Formato de um cheiro FLEX

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

%{ int numChars=0; %} %% . { numChars++; p r i n t f ( "%s " , y y t e x t ) ; } \n {

3

13 14 15 16 17 18 19 20 21 22 23 24

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 ) ; }

1.3.1

Declaraes

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

/ D e f i n i o da v a r i v e l numChars / %{ int numChars=0; %}

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

/ 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.

1.3.2

Regras (denio de padres e aces)

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.

4

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

.

{ numChars++; p r i n t f ( "%s " , y y t e x t ) ; }

\n

{ numChars++; p r i n t f ( "\n" ) ; }

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).

1.3.3

Rotinas em C de suporte

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

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

5

A funo yylex() evoca o analisador lxico gerado pelo ex que processar as expresses regulares anteriormente descritas (ver seco 1.3.2).

1.4

Exemplo mais elaborado

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

%{ 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]

%% 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.

1.5

Propostas de exerccios

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;

6

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;

Entrada 123 abc 12.45 s 245 xyz xyz 2 abc 45 cc

Sada 123 12 45 245 2 45

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);

7

1.6

Ambiente de trabalho

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.

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.

1.7

Resumo de comandos UNIX teis

Na tabela 1.2 so apresentados os comandos que permitem fazer mudana de directrio e mostrar qual o directrio actual.

Comando cd cd .. cd pwd

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