1
00:00:00,719 --> 00:00:04,690
welcome back to part number three

2
00:00:04,690 --> 00:00:08,250
about bars am we

3
00:00:08,250 --> 00:00:11,570
had they find some very simple parsers

4
00:00:11,570 --> 00:00:14,740
then we developed in the second part

5
00:00:14,740 --> 00:00:18,010
a few bars urge to go to a bar several

6
00:00:18,010 --> 00:00:21,320
and you several bars in a row and

7
00:00:21,320 --> 00:00:25,279
even doe the bars that we have defined
are very primitive

8
00:00:25,279 --> 00:00:29,160
they are already powerful enough to
parse

9
00:00:29,160 --> 00:00:32,920
a.m. arithmetic expressions that have
like no deep structure

10
00:00:32,920 --> 00:00:36,390
and and that's what we're going to do
indicia lost

11
00:00:36,390 --> 00:00:43,070
part of this lecture on barging here's
the expressions that we're going to bars

12
00:00:43,070 --> 00:00:46,890
and be want to have simple expressions
that

13
00:00:46,890 --> 00:00:51,870
are built from simple digits with
addition and multiplication

14
00:00:51,870 --> 00:00:55,030
I'm expression Gandhi me brent is sized

15
00:00:55,030 --> 00:01:00,239
and moreover we want times to bind
stronger

16
00:01:00,239 --> 00:01:03,710
and blush and we won't bode have them to

17
00:01:03,710 --> 00:01:07,900
associates to the right so what does
that mean if we have a-plus B-plus she

18
00:01:07,900 --> 00:01:12,729
we want to parse that a plush open
brandy plushie

19
00:01:12,729 --> 00:01:16,390
and every at 8 blush be dime si

20
00:01:16,390 --> 00:01:19,979
we want to impart that as a plus be dime
si

21
00:01:19,979 --> 00:01:24,310
alright so this is fairly and
conventional

22
00:01:24,310 --> 00:01:28,259
just arithmetic expressions so how are
we going to

23
00:01:28,259 --> 00:01:32,250
emblem and this using those very very
simple parser

24
00:01:32,250 --> 00:01:35,420
that we defined in the previous two
sections

25
00:01:35,420 --> 00:01:40,180
well the first thing ever going to do as
you're going to write down

26
00:01:40,180 --> 00:01:44,140
a grammar for and these expressions

27
00:01:44,140 --> 00:01:47,750
and an if you have taken

28
00:01:47,750 --> 00:01:52,159
course in going by Lahr sore formal
languages are

29
00:01:52,159 --> 00:01:55,270
you know you lookin and a programming
language

30
00:01:55,270 --> 00:01:59,659
definition in the back where the grammar
of the languages defined

31
00:01:59,659 --> 00:02:04,060
you will find a grammar that looks very
similar to this show

32
00:02:04,060 --> 00:02:07,820
there's an expression there's a term
there's a factor

33
00:02:07,820 --> 00:02:11,500
and East three productions are used to
encode

34
00:02:11,500 --> 00:02:15,640
and the binding up the expressions and
they can

35
00:02:15,640 --> 00:02:20,030
defected these are defined like this in
this regard to form

36
00:02:20,030 --> 00:02:24,610
and an and coach

37
00:02:24,610 --> 00:02:29,420
the ad shows a diff shell an expression
is a term plus an expression

38
00:02:29,420 --> 00:02:32,910
our Term a term is a factor dimes a derm

39
00:02:32,910 --> 00:02:37,990
are a factor factors a digit or
apprentice eyes expression

40
00:02:37,990 --> 00:02:42,209
and a digit as well digit alright show
that your day

41
00:02:42,209 --> 00:02:46,750
recursion and bottoms but as I said

42
00:02:46,750 --> 00:02:50,200
this is real standard encoding

43
00:02:50,200 --> 00:02:55,270
of expressions in a grammar I'm

44
00:02:55,270 --> 00:02:58,580
now what we're going to do is we're
going to much Josh

45
00:02:58,580 --> 00:03:01,709
this a grammar little bit and again

46
00:03:01,709 --> 00:03:05,280
the it's also a very common every book
an

47
00:03:05,280 --> 00:03:08,470
on compiler she'll do this and often

48
00:03:08,470 --> 00:03:13,270
and grammars are defined addition their
way we'll do it they saying

49
00:03:13,270 --> 00:03:17,350
an expression is a term followed by

50
00:03:17,350 --> 00:03:22,150
plus an expression or the empty string

51
00:03:22,150 --> 00:03:25,980
are absent on this in the AM departure
and it doesn't recognize anything

52
00:03:25,980 --> 00:03:29,450
an and then term as a factor

53
00:03:29,450 --> 00:03:33,269
and followed by start term or

54
00:03:33,269 --> 00:03:37,880
an again the bars are dead only
recognizes the

55
00:03:37,880 --> 00:03:41,400
an the empty input a game

56
00:03:41,400 --> 00:03:44,590
so if we take this weekend

57
00:03:44,590 --> 00:03:48,049
now immediately translated

58
00:03:48,049 --> 00:03:51,959
this definition here which is recursive
here

59
00:03:51,959 --> 00:03:55,260
in expression is defined in their human
expression

60
00:03:55,260 --> 00:03:59,500
but there's first-term and and its
recognizes the blusher

61
00:03:59,500 --> 00:04:03,170
is here expression recognizes a derm

62
00:04:03,170 --> 00:04:06,320
an a-plus and an expression

63
00:04:06,320 --> 00:04:10,680
and then its returns an the expression

64
00:04:10,680 --> 00:04:14,610
blush the term plus the expression and
then this rom

65
00:04:14,610 --> 00:04:18,440
is the and the anti-gay

66
00:04:18,440 --> 00:04:22,039
alright so an you will image in the

67
00:04:22,039 --> 00:04:24,090
return getter

68
00:04:24,090 --> 00:04:27,660
and in his aim for term and the same

69
00:04:27,660 --> 00:04:32,680
for factor so in some sense that going
up to grammar

70
00:04:32,680 --> 00:04:35,790
an has a one to one correspondence

71
00:04:35,790 --> 00:04:39,130
and when this recursive and

72
00:04:39,130 --> 00:04:43,120
an expression here and that's that then
I think so

73
00:04:43,120 --> 00:04:47,169
and some sense and decision the spartan

74
00:04:47,169 --> 00:04:52,280
Combinator says they're called are like
an internal DSL so incentive riding a

75
00:04:52,280 --> 00:04:53,090
grammar

76
00:04:53,090 --> 00:04:57,330
in some x31 the fine language like ya
cadillacs

77
00:04:57,330 --> 00:05:00,840
compiling that into another language

78
00:05:00,840 --> 00:05:04,960
we can't do this all that has gone and
use all the facilities

79
00:05:04,960 --> 00:05:08,030
haskell to define helper functions and
shown

80
00:05:08,030 --> 00:05:11,520
and parsers are 10 I think

81
00:05:11,520 --> 00:05:15,530
the the most elegant

82
00:05:15,530 --> 00:05:19,530
you know internal DS house and that you
can imagine

83
00:05:19,530 --> 00:05:24,240
and and as I said you can do very
sophisticated parsers

84
00:05:24,240 --> 00:05:27,479
and you can push this I dear pretty far

85
00:05:27,479 --> 00:05:30,570
now

86
00:05:30,570 --> 00:05:34,620
next thing is we're going to define and
evaluator

87
00:05:34,620 --> 00:05:38,030
that takes a strain barges the and

88
00:05:38,030 --> 00:05:41,479
tries to parse the string as an
expression

89
00:05:41,479 --> 00:05:45,370
and then return the resulting value

90
00:05:45,370 --> 00:05:49,210
and if you we go back here

91
00:05:49,210 --> 00:05:52,419
initiated for already

92
00:05:52,419 --> 00:05:55,669
evaluating the an expression

93
00:05:55,669 --> 00:05:59,000
as for parsing it biggest for parsing
the plush

94
00:05:59,000 --> 00:06:02,320
operator and then we're taking the term
amor

95
00:06:02,320 --> 00:06:05,479
adding the result of parsing the
expression show

96
00:06:05,479 --> 00:06:08,550
the result of this is already a parser
offend

97
00:06:08,550 --> 00:06:12,010
so instead of we're not even creating a
parse tree

98
00:06:12,010 --> 00:06:15,410
for immediately after parsing we're
evaluating

99
00:06:15,410 --> 00:06:19,410
the expression so that's what you see
here we parse the expression

100
00:06:19,410 --> 00:06:22,729
if in the end to it since this return

101
00:06:22,729 --> 00:06:26,030
returns and either a

102
00:06:26,030 --> 00:06:31,000
empty list or a single to left if it
returns a single to left leading the

103
00:06:31,000 --> 00:06:32,719
hatchery take that value

104
00:06:32,719 --> 00:06:36,550
we take the first element which was the
number and then there's the rest

105
00:06:36,550 --> 00:06:40,780
the strain if this fails to parse the
heads will throw an error

106
00:06:40,780 --> 00:06:45,110
and this whole thing will fail so let's
see here

107
00:06:45,110 --> 00:06:48,190
if you're barging two dimes three-plus
for

108
00:06:48,190 --> 00:06:52,390
that should return two dimes 36 pledge
for

109
00:06:52,390 --> 00:06:55,850
as dan and guess what

110
00:06:55,850 --> 00:07:01,000
that's the value we get and if we're
evaluating

111
00:07:01,000 --> 00:07:04,060
two dimes to replace for well we should
get

112
00:07:04,060 --> 00:07:07,770
is 3 bids for Saban times two ish 14

113
00:07:07,770 --> 00:07:10,840
guess what is message as expected

114
00:07:10,840 --> 00:07:16,410
okay in the exercises you will do

115
00:07:16,410 --> 00:07:19,800
an sever all things red parsers

116
00:07:19,800 --> 00:07:25,870
and in particular an one other thing
said you will do

117
00:07:25,870 --> 00:07:30,480
issue you will have to implement the
sequencing operator

118
00:07:30,480 --> 00:07:34,490
that we used but didn't define so

119
00:07:34,490 --> 00:07:40,670
we have defiant various operators on
partition one of the essential launch

120
00:07:40,670 --> 00:07:44,510
these sequential composition we didn't
define

121
00:07:44,510 --> 00:07:47,690
and thats the main exercises this week

122
00:07:47,690 --> 00:07:51,110
so and happy hacking

123
00:07:51,110 --> 00:07:54,830
make sure you do your homework and see
you next week

124
00:07:54,830 --> 00:07:55,530
i buy