Return to Video

04-46 Parse Trees

  • 0:00 - 0:02
    Agora temos todo o maquinário de que precisamos
  • 0:02 - 0:04
    para dizer se um string é válido.
  • 0:04 - 0:06
    Entretanto, isso ainda não é suficiente.
  • 0:06 - 0:09
    Você se lembra das árvores de derivação de que falamos anteriormente?
  • 0:09 - 0:12
    Nós relamente vamos precisar delas, também,
  • 0:12 - 0:15
    para que nossos programas HTML e JavaScript
  • 0:15 - 0:19
    possam ser interpretados -- para que possamos dar a eles o significado correto.
  • 0:19 - 0:22
    Então, escrevi aqui uma gramática para expressões aritméticas bastante padrão.
  • 0:22 - 0:24
    Uma expressão pode ser um número -- number,
  • 0:24 - 0:26
    ou exp plus exp,
  • 0:26 - 0:28
    ou exp minus exp, ou, talvez,
  • 0:28 - 0:30
    not exp, como, por exemlo, -3.
  • 0:30 - 0:32
    E vamos querer construir a árvore de derivação para isso.
  • 0:32 - 0:35
    Desta vez, eu escrevi os tokens como plus, minus e not,
  • 0:35 - 0:37
    ao invés dos símbolos + ou -.
  • 0:37 - 0:39
    Esta é uma escolha -- podemos fazer isso da forma como quisermos.
  • 0:39 - 0:41
    E o formato particular que eu vou usar
  • 0:41 - 0:44
    para nossa árvore de sintaxe abstrata é
  • 0:44 - 0:47
    tuplas aninhadas, ou listas aninhadas, em Python.
  • 0:47 - 0:51
    Então, se eu acabar usando esta regra: exp -> number,
  • 0:51 - 0:54
    vamos retornar a tupla:
  • 0:54 - 0:56
    ("number",5) -- se a entrada for 5.
  • 0:56 - 1:00
    De modo similar, se a entrada for algo como -5,
  • 1:00 - 1:05
    vamos retornar ("not',("number",5)) --
  • 1:05 - 1:07
    note o aninhamento.
  • 1:07 - 1:09
    Então, digamos que eu chame este número de número1.
  • 1:09 - 1:11
    Vamos querer retornar essa tupla:
  • 1:11 - 1:14
    ("number", 1) -- "number", entre aspas, de modo que possamos saber o que é --
  • 1:14 - 1:16
    seguido do valor do token.
  • 1:16 - 1:20
    Se isso fosse o número 2, em nossa regra de redução --
  • 1:20 - 1:25
    não exp -- eu gostaria que isso fosse preenchido com 2.
  • 1:25 - 1:27
    Se aqui, isso fosse um 3,
  • 1:27 - 1:29
    eu gostaria de retornar "binop" --
  • 1:29 - 1:32
    isso significa operador binário (binário significa com 2 operandos).
  • 1:32 - 1:34
    Então, coisas como plus, minus, times e divide,
  • 1:34 - 1:36
    são oerações aritméticas que têm 2 argumentos --
  • 1:36 - 1:38
    uma à esquerda e um à direita --
  • 1:38 - 1:42
    e chamamos isso de operadores binários -- como uma classe -- apenas para economizar espaço.
  • 1:42 - 1:44
    Mas, seja lá qual for a terceira expressão,
  • 1:44 - 1:47
    isso é o que eu quero que seja esta subárvore --
  • 1:47 - 1:49
    esta subparte da minha tupla.
  • 1:49 - 1:51
    Então, assim como vimos antes como podemos
  • 1:51 - 1:55
    codificar regras de token em Python,
  • 1:55 - 1:58
    e fazer algum processamento, tal como eliminar aspas,
  • 1:58 - 2:00
    depois de termos especificado como token funciona,
  • 2:00 - 2:02
    usando expressões regulares,
  • 2:02 - 2:05
    vamos ver que existe uma maneira similar de
  • 2:05 - 2:07
    fazermos isso para regras de gramática, em Python.
  • 2:07 - 2:10
    Deixe-me explicar um pouco mais sobre o que acontece aqui.
  • 2:10 - 2:12
    Este formato é totalmente arbitrário,
  • 2:12 - 2:14
    mas será muito fácil de utilizar
  • 2:14 - 2:16
    para exercícios e para testar nosso conhecimento.
  • 2:16 - 2:19
    Para tokens, usamos "t_" para significar
  • 2:19 - 2:21
    que estamos definindo um token.
  • 2:21 - 2:23
    Para regras do parser,
  • 2:23 - 2:25
    vamos usar "p_"
  • 2:25 - 2:27
    para definir o nome de uma regra do parser.
  • 2:27 - 2:29
    E aqui -- apenas para nos ajudar --
  • 2:29 - 2:32
    vamos escrever o que é o lado esquerdo da regra.
  • 2:32 - 2:34
    Isso é como fazemos o parsing de uma expressão,
  • 2:34 - 2:36
    quando essa expressão é um número.
  • 2:36 - 2:39
    Assim como nossas regras de token eram, de certo modo,
  • 2:39 - 2:42
    funções por trás deste objeto t,
  • 2:42 - 2:46
    nossas regras de parsing são funções por trás deste objeto p.
  • 2:46 - 2:49
    E eisso é a árvore de derivação --
  • 2:49 - 2:51
    ou, mais precisamente, um certo número de árvores de derivação.
  • 2:51 - 2:53
    Aqui está escrita a nossa regra,
  • 2:53 - 2:55
    e isso é muito semelhante a
  • 2:55 - 3:00
    exp -> number, exceto que não existe uma boa representação para a seta e,
  • 3:00 - 3:02
    ao invés disso, escrevemos simplesmente : -- por convenção --
  • 3:02 - 3:05
    mas você pode pensar nisso como sendo a seta.
  • 3:05 - 3:08
    Então, isso é: exp pode ser reescrita como number --
  • 3:08 - 3:10
    e simplesmente colocamos isso entre aspas, como um string.
  • 3:10 - 3:13
    E aqui temos que dizer a Python -- ou à nossa biblioteca de parsing --
  • 3:13 - 3:16
    como construir a árvore da sintaxe abstrata.
  • 3:16 - 3:20
    p[0] é a árvore da sintaxe abstrata que retornamos.
  • 3:20 - 3:25
    A numeração aqui é que cada um dos elementos da nossa regra da gramática
  • 3:25 - 3:28
    tem um número, exceto este :.
  • 3:28 - 3:30
    Portanto, a expressão à esquerda é o elemento 0;
  • 3:30 - 3:32
    este number é o elemento 1.
  • 3:32 - 3:35
    Então, a árvore de derivação que eu quero associar a esta expressão,
  • 3:35 - 3:37
    quando tivermos terminado,
  • 3:37 - 3:41
    é a tupla que eu construo combinando a palavra "number"
  • 3:41 - 3:43
    com o valor deste token corrente.
  • 3:43 - 3:45
    Vou mostrar mais um exemplo
  • 3:45 - 3:47
    e então vai ficar um pouco mais claro.
  • 3:47 - 3:49
    Aqui, masi uma vez, eu começo com p_ --
  • 3:49 - 3:51
    vamos fazer isso para todas as nossas regras de parsing.
  • 3:51 - 3:54
    Aqui está o que eu estou querendo analisar: quero dizer como fazer o parsing de uma expressão.
  • 3:54 - 3:57
    Podem haver diferentes maneiras de fazer o parsing de uma expressão:
  • 3:57 - 3:59
    ela pode ser um number, ou not exp.
  • 3:59 - 4:02
    Então usamos aqui outro _ para sermos um pouco mais específicos.
  • 4:02 - 4:05
    E aqui, escrevi minha regra da gramática --
  • 4:05 - 4:07
    quase como em Inglês -- e, novamente, este :
  • 4:07 - 4:10
    representa a -> que escreveríamos usualmente.
  • 4:10 - 4:12
    Abaixo disso, eu escrevi
  • 4:12 - 4:15
    como construir a árvore da sintaxe abstrata.
  • 4:15 - 4:18
    Esta expressào é a de indice 0,
  • 4:18 - 4:21
    esta expressão é a 2, e queremos que nossa
  • 4:21 - 4:23
    árvore de parsing para o índice 0
  • 4:23 - 4:26
    seja a tupla que obtenho colocano a palavra "not"--
  • 4:26 - 4:30
    para que eu saiba o que é -- na frente da árvore de derivação para a expressão 2.
  • 4:30 - 4:34
    Se eu vejo a entrada: not 5,
  • 4:34 - 4:38
    e executo essas duas regras, na ordem correta --
  • 4:38 - 4:40
    esta primeiro, e depois esta --
  • 4:40 - 4:42
    obtenho esta árvore:
  • 4:42 - 4:45
    ("not", ("number",5)) --
  • 4:45 - 4:47
    observe o aninhamento.
  • 4:47 - 4:49
    Alternativamente, eu poderia desenhar isso assim.
  • 4:49 -
    Isso é apenas a maneira de codificar em Python esta representação visual.
Title:
04-46 Parse Trees
Description:

04-46 Árvores de Derivação

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
04:54
Lucilia Figueiredo edited Portuguese, Brazilian subtitles for 04-46 Parse Trees
Lucilia Figueiredo added a translation

Portuguese, Brazilian subtitles

Revisions Compare revisions