Types 20+ lines of Haskell program in a single breath, then gets 0 warnings or errors from GHC, then goes on as if it is totally normal...

@jeremiahglover7562

4 жыл бұрын

Profile picture checks out.

@petros_adamopoulos

4 жыл бұрын

Because it is normal. He's done this kind of code many times before.

@warpmonkey

4 жыл бұрын

And no StackOverflow screen up!

@maxtaylor3531

4 жыл бұрын

The Graham Haskell Compiler

@akoppela

4 жыл бұрын

That's totally normal

So glad my university teaches Haskell. Even if you dont ever use it in your work, learning to program in that language makes you a better programmer and writing a compiler is usually a thing that Haskell will be used for.

@sebastiangudino9377

7 ай бұрын

Yup, compilers are one of the more functionally pure things you can program. They are VERY complex, but they just are fancy "String input, string output" machines when you look at the big picture

@nanthilrodriguez

5 ай бұрын

Now go learn apl

The key (which IMHO was not so well explained in the video) is that you have a function (parser combinator) that takes other functions (parsers) as input, and produces a function (more complex parser) as a result. This is rather similar to "normal" recursive-descent parsing, except you don't do the combining yourself, and instead let the parser combinator do it for you.

@Dan-gs3kg

4 жыл бұрын

That's one of the key takeaways of Functional programming, "Higher-Order Functions", or functions that use other functions as parameters. A short and sweet paper is the Functional Pearl about Sixth-Order Functions. Why would you need a Sixth-Order Function? When you are using parser combinators!

@Verrisin

Жыл бұрын

Doesn't sound like something I would need a video for. It's clear from the name "parser combinator". It's clearly something that combines parsers into a parser, and then it's obvious those are then combined by further combinators and that's how you can build the whole root parser. - This video shows how to do that with monadic combinators, and the which I guess is just a concat function for the lists.

@cparks1000000

8 ай бұрын

The operator is most likely a custom operator definited in the package.

Had to pause the video say, after studying parsers a lot recently I think the beginning explanation is on of the best of what a parser actually is

@petros_adamopoulos

4 жыл бұрын

I think it sounds like an ideal explanation, when you know the subject well beforehand, interesting.

"It doesn't matter if you know any Haskell, because I'll be explaining everything as I go along. So you won't understand a thing either way."

@JNCressey

4 жыл бұрын

> claims we don't need to know Haskell > isn't explicit about which words are imported from his module and which are keywords.

@doublex85

4 жыл бұрын

As of the finished module in 19:35: 　 The import declaration allows use of the exported definitions from module Parsing. There's also a standard library module Prelude which is imported by default if not mentioned. 　 Equals= defines values. 　 Do and >=) operator, i.e.: do { b >= (\b -> c) 　 Module Prelude exports typeclass methods add(+), multiply(*), alternate(), bind(>>=), and return, and also exports the implementations of (+) and (*) for whichever of the various number types the end program might use. The defaulting rules in the REPL session seem to select the Integer type. 　 Module Parsing defines type Parse, function char, and method implementations for (), (>>=), and return. The bind(>>=) method does all the heavy lifting of combining two parsers into one larger parser. 　 The main module defines functions expr, term, and factor.

The videos of this guy are a treasure, thanks a lot!

say it takes a string as an input and returns a tree as an output one...more...time

@PauxloE

4 жыл бұрын

... and then the example parser doesn't even return a tree, but just an integer.

@cheaterman49

4 жыл бұрын

@@PauxloE Agreed - I guess the video couldn't get much longer though, but I'd have loved to see his parser return an AST and then implement the logic to interpret it!

@WorBlux

4 жыл бұрын

@@PauxloE It evaluates the tree as it goes along., and it is walking the tree even though we're not seeing it. To get a tree, you'd modify the grammar to so that the do block returns a tree, rather than the the result of evaluating the math expression. The biggest problem I see with this toy example is there's no error handling. Malformed input can just get lost without affecting the tree or warning the user.

@casperes0912

4 жыл бұрын

gi70st I can fix that for you... It takes an array of chars and gives back an AST

@JNCressey

4 жыл бұрын

It was so confusing how he did that switcheroo. I was there thinking "how does `return (x+y)` make it produce a node `"+"` with branches `x` and `y`?" And even after acknowledging that this is really evaluation, he kept calling it a parser, even though the beginning of the video he insisted that what a parser is to him is something that produces a tree as output.

Thanks, that was very illuminating. And it’s nice to see Haskell being used in a practical setting.

Regarding the "list of results" remark, maybe a fun example would be a parser that can handle all possible interpretations of "time flies like an arrow, fruit flies like a banana"

@ais4185

4 жыл бұрын

That's a cool one.

What an excellent complement to the material found in his book! Hope to see more

WOW! Anyone saw the beautiful recursion in the definition of these expression parsers? I don't have the kind of brain to quickly think recursively like this

Graham Hutton. Your Haskell book was incredibly useful!! Never clicked so fast on a computerphile video. Parsing in Haskell was a bit hard in the beginning though.

@keestv3116

4 жыл бұрын

what is the name of the book? okok i just google it. =D

@elgalas

4 жыл бұрын

@@keestv3116 Programming in Haskell :)

@AlexKavanagh29x

4 жыл бұрын

I, too, used the book. Excellent resource for starting Haskell.

@DutchmanDavid

4 жыл бұрын

> Parsing in Haskell was a bit hard in the beginning though. Getting used to all those new operators (, , , among others) was brain-breaking, initially.

@TheSpacecraftX

4 жыл бұрын

Oh he wrote that book. That book got me through first year in uni. I bought it in desperation for my resit. It was the only module I had to resit and I still harbour a special hatred of Haskell.

I did this with Java, I wrote a postfix expression parser that could do symbolic differentiation and simplification. I used polymorphism to implement the tree structure

Excellent explanation, very interesting to watch!

This should be a whole series on its own channel... I think a channel dedicated to programming the simple things. Things like this video, but things like... Graphics, calculate a line, circle, plasma, transparncy, sprites, theres heaps and heaps of things like that, 3D rotation vertex and bitmap.. processing raw data by a microphone is another 100 videos. I could go on... Maybe

Having trouble parsing Grahams accent. Sounds like its from everywhere in the UK at once! Fascinating

@iliakorvigo7341

4 жыл бұрын

He sounds unambiguously Irish to me, but as far as I know, he is actually Scottish.

One thing here is that parser he implemented does binary opetator evaluation right-to left. Left-to-right binary operators are more involving.

Wow! So cool how much you can do in a few lines of Haskell. Like defining a grammar, and a parser for it!

It is a bit annoying that the camera switches from head to laptop to screen constantly

Where was this video for my Language Engineering unit at university?! This would've been so useful to refer to!

Awesome and excellent video as usual

Excellent tutorial.

Great video! I've written some parsers in Haskell, but Prof. Hutton makes it look easy.

More videos with prof Hutton and functional programming. My favorite topic

Shouldn't (some digit) return multiple results, parsing 1, 2 or 3 digits? Otherwise the parser wouldn't return all possibilities right?

More of this, please! Graham is an outstanding teacher.

"4 and half screen fulls and is full fledged and can basically implement any parser you like" - mic drop

Beautiful! Respect!

So interesting! Thank you so much! That is quality teaching.

It's funny, it feels like Haskell makes a lot more sense to me when used in this context? I don't know, I usually cringe a bit when seeing the syntax but this example falls beautifully into place and feels very elegant? Also, the stdlib Parsing library being likes a hundred lines is pretty interesting too, probably both this and the example in the video play very well with the strengths of the language?

@JobvanderZwan

4 жыл бұрын

It's not just you - there's a reason quite a few experimental compilers are implemented in Haskell.

@cheaterman49

4 жыл бұрын

@@JobvanderZwan Thanks for the info - makes a lot more sense to me than people pushing Haskell as a general-purpose programming language. At least that's how I feel right now (I do Python for a living), but I might revise my judgement in the future :-)

@samm7334

4 жыл бұрын

Agreed. In my current lecture we're implementing a parser in OCaml (close enough I guess). The thing is that parser/compiler need a lot of things that are close to theory (recursion, trees etc...) and pattern matching, all of which is at home in any functional language.

Is Hascal some sort of hybrid language?

Just wrote an abstract syntax tree in my utils package for tokenizing symbolic math expressions, would be cool if you guys went over how ASTs are used in compilers / interpreters as well

@Dan-gs3kg

4 жыл бұрын

That gets into recursion schemes. Instead of consuming strings, you consume and rebuild trees. There's quite a bit involved there as different schemes have drastically different capabilities. The important bit is that those pieces compose well, and have some very nice optimisations.

WOW... I just had to wrote a parser and evaluator, in Kotlin and I had 3 classes, working in conjunction to get final answer. While this feels like magic.

13:39 what happens if there is no "-", how does Haskell know that it has now to use the nat parser?

@rastislavsvoboda4363

3 жыл бұрын

instance Alternative Parser where empty = P (\inp -> []) p q = P (\inp -> case parse p inp of [] -> parse q inp [(v, out)] -> [(v, out)]) this special 'or' operator executes left side parsing (in this case '-' char followed by natural number), if it succeeds it returns result, if not it will return right side parsing result (in this case just natural number)

Why don't you use Maybe monad instead of List monad? I think it would be better and more intuitive. I mean: type Parser a=String->Maybe (a,String)

How would one use this with left recursion and left associativity?

@haskellhutt

2 жыл бұрын

One of the limitations of top-down parsing methods such as functional parsing is that left recursion results in parsers that loop. One possible solution is to transform the grammar first to eliminate the left recursion. Another is to define special-purpose combinators to parse operators that associate to the left.

Sorry, but back in the day, I used Lex and YACC. This takes all the fun out of it

Maybe it's because I don't know haskell but it's unclear to me how expr chooses whether to do the '+' branch or not

@johngibson4874

2 жыл бұрын

It backtracks. It tries to do the '+' case and if it can't it backtracks and does just the term case.

Where did the tree go? At 5:02 he deletes the tree and I didn’t see it again!

@bingloveskoki

4 жыл бұрын

He replaced the Tree-type with an arbitrary Type 'a'. So a parser can now calculate anything you want. You might want to keep calculating a tree, then a would be equal to Tree or you want to calculate something different like e.g. an integer (a=Int).

@doublex85

4 жыл бұрын

To be specific, the 'a' is a type variable. In Java, C++, Rust, or similar syntaxes it would be the T in Parser. In Haskell syntax, types and their parameters are written one after the other without brackets, just like Haskell values. Some examples and their C-like equivalents: List (Pair Int Char) = List Pair (List Int) Char = Pair List Pair Int Char = List (this is probably an error.) Parser a = Parser In C-like syntax type variables have to be introduced explicitly, such as with the template keyword in C++, but in Haskell you know any name that starts with a lowercase letter is a variable. Again, just like in term-level expressions.

I very much like using functional programming for translator writing. It's explicit and elegant.

Thanks for such visual and enlightening video. Next time, however, I'd rather see this kind of video (coding) as a screen cast, rather than camera jumping back and forth. Professors head talking just obscured the point he wanted to make about the primitives library. Overall, it was surprising how the parsing library neatly applied to the problem.

Brilliant! Thank you!

This is neat but a little too simple to be useful, imo. For example, how do you also parse subtraction ("-") and division ("/") and also allow any term to be negated (for example "2 + 3 * 4 / -(-10/5)" -- Note the "-" in front of the compound term. Just a bit more complexity would allow us to see how the parser source code scales as the number of terms increase.

@samm7334

4 жыл бұрын

Of course it's not useful. It's an example for explanation no industry standard parser. Subtraction and division are incredible similar to their counterparts. A negation would be a different rule like "-" expr but this introduces a parse conflict since the "-" can be subtraction or negation (so called "shift/reduce conflict). That needs to be handled but suddenly the video would be 1hr long and way harder to follow.

@JNCressey

4 жыл бұрын

> parse expr "2 + 3 * 4 / -(-10/5)" *Drake nah meme > 2 + 3 * 4 / -(-10/5) *Drake yeah meme

@samm7334

4 жыл бұрын

@@JNCressey I just realized that I want all my compiler errors to be presented as memes

@gabe_owner

4 жыл бұрын

I think you're referring to the difference between a binary and unary minus operator. / has essentially the same precedence as multiplication so it shouldn't be hard.

@MidnighterClub

4 жыл бұрын

@@gabe_owner Well partially, yes, I'd like to see how both unary and binary operators get handled. But I'm also not seeing exactly how operators with equal precedence (like +- and */) get handled with this scheme as well, so an example of that would be helpful.

So if we wrote some code that ran parsers in an infinite loop and then buried that computer would it produce infinite trees and thus solve deforestation?

So, your definition of parser includes both the tokenizer and the syntax checker?

@Dan-gs3kg

4 жыл бұрын

You can say that a tokeniser is a parser from a String to a List of Tokens. Rinse and repeat with the List of Tokens until you have what you want.

More haskell please, I love it

Cutting back and forth between the computer, the screen, and the speaker is not the best decision. It's very frustrating.

I’am try to write a functional parser in Scheme!

Thank you for this video. but why do I get this exception? I'm running it on GHCi 7.6.3 *Parsing> parse (some digit) "123" *** Exception: Parsing.hs:38:10-21: No instance nor default method for class operation GHC.Base.return I also get this warning when I load Parsing.hs [1 of 1] Compiling Parsing ( Parsing.hs, interpreted ) Parsing.hs:38:10: Warning: No explicit method or default declaration for `return' In the instance declaration for `Monad Parser' Ok, modules loaded: Parsing.

@qzbnyv

4 жыл бұрын

Apple, definitely upgrade your GHC. Try not to use the versions of GHC that come with the package managers of various OS choices as they tend to be quite out of date. Use the curl (or wget) install scripts that you’ll find on the websites for either of the things I’m about to mention in quotes. Either install the Haskell “Stack” tool for managing isolated sandboxed versions of GHC on your system (so you can have different projects operating with different GHC versions) or use “ghcup” to install Cabal for you to do something similar. But yeah, avoid whatever is in your package manager like the plague. And GHC 7.6.3 is pretty out of date with how monads are implemented. There’s been some significant language shifts since then.

@qzbnyv

4 жыл бұрын

Apple also add the line “return = pure” within the Monad instance declaration (...just above the definition for (>>=) is where you’d normally put it).

@Eagle-jo8cx

4 жыл бұрын

NWN thank you very much! Unfortunately I need to use specifically this version for my university coursework

@qzbnyv

4 жыл бұрын

Apple that’s a shame. What university/subject is this? Lectures should really update their course materials + backend. In GHC 7.10 the “Functor-Applicative-Monad Proposal” was implemented that made all Monads have Applicative as a superclass, which is a pretty big change and something that should be part of your learning ecosystem.

12:56 "And then I'm gonna *simply* return it" Ah yes, that's what happens there, no magic at play at all :v Yeees :v

Looks rather like recursive descent parsing to me.

@_aullik

4 жыл бұрын

its a variation of it. Basically a functional/monadic version of it. Solves some problems like running out of Stack. It also makes backtracking a lot easier and the syntax smoother (but more complex). It also means that you can skip the lexer part. recursive descent rarely works well in imperative languages and it has a lot of boilerplate. It works a lot better in functional and is a lot compacter. EDIT: The correct term is "parser combinator" when you wanna lookup more on google/wikipedia.

@Ceelvain

4 жыл бұрын

@@_aullik Backtracking? Wouldn't one want his grammar deterministic? So that, you know, parsing time is linear in the length of the input.

@_aullik

4 жыл бұрын

​@@Ceelvain Yes and no. Specially if you are context sensitive (which is completely possible here) backtracking can give you some nice advantages. Obviously for the cost of performance. That being said, if you keep the parts where you use backtracking short and/or use mnemonics. This way the performance overhead is pretty slim. If you make mistakes with this, it will cost you performance. The big advantage however is fast prototyping and relatively easy unit testing and that you can do things you cant with regular parser generators. Best case performance is close to parser generators as you can skip lexing. What I have seen in the real world however is usually quite a bit worse. However if I only have to build parser for smaller (max 1k lines) Inputs I prefer this option.

@frabert

4 жыл бұрын

One way that parser combinators differ from recursive descent parsers is that they are declarative, rather than imperative. This means that, for example, you might choose to implement the resulting parser as a LR(1) parser, or maybe using CYK, because the parser itself does not describe the implementation, but only the grammar. Of course, all the actual parser combinator libraries I know use recursive descent in the end :)

@lhpl

4 жыл бұрын

​@@_aullik Recursive descent has worked very well in imperative languages for many decades. As for skipping lexing, that is a matter of optimisation, as I understand it.

That was awesome. Thank you!

Neat but you lost me when you started implementing the grammar. Also would have liked to see the tree before it was evaluated.

@Dan-gs3kg

4 жыл бұрын

The implementation reflects the grammar. Alternative parse paths are separated by (), where alternate expressions of the same term are separated by (|).

I'm wondering, is a parser a function that takes a string as an input and gives a tree as an output?

Interesting. How do combinator parsers compare with table parsers like Earley parsers? Is it possible yo combine approaches?

@tomyamahito

4 жыл бұрын

s/yo/to/ !

BTW what is the font you used in this video?

So it you have a structure of sort with leveled information and break out thing that meet specific conditions, is that parsing your explanation is so filled with lingo? I hear you talk aaout returning trees and pairs is that a request for being a parser. What about if you split up a string consisting of a leveled record tree" maybe first into substrings knowing which type of information in each string and the sub iterate the record structures within them using the record brackets and identifiers isn't that parsing top down?

@JmanNo42

4 жыл бұрын

What is the main definition of a parser, i thought it was breaking out information from structured data using rules?

@framegrace1

4 жыл бұрын

@@JmanNo42 Yep, and the structured data is always a tree when calculating expressions. Operations always return a single result.

Nice video. Would like it if you'd switch screens less to make it feel more "dynamic" while there's code being shown.

What is the Haskell parsing library without IO, Maybe, Option and Exceptions?

@bingloveskoki

4 жыл бұрын

Well, the same I guess.

@TarasMazepa

4 жыл бұрын

@@bingloveskoki Nah, this one is just a toy :)

@gabe_owner

4 жыл бұрын

painful

oh, do more haskell please :DDDD

I already know Haskell and quite a number of monads already but haven't got time to learn parser as a monad. So this video is perfect for me.

@Dan-gs3kg

4 жыл бұрын

It's effectively the State Monad.

@ancbi

4 жыл бұрын

@@Dan-gs3kg If all parsers always produce singleton list, then parser monad = state monad as you said. So parser monad could be used as state monad. *But can you show the converse?* because that is what it means for me to say 'parser monad is effectively state monad' and I don't yet see how.

@Dan-gs3kg

4 жыл бұрын

@@ancbi I'm a bit fast and loose here, but you can see the correspondence between say: > Parser a = P (String -> (a, String)) > State s a = S (s -> (a, s)) Where (s ~ String), and (~) is Type Equality The more general statement: > Parses a = P (String -> [(a, String)]) Is a bit different, but then we can also make a more general statement about what the State effect is. > StateT s m a = S (s -> m (a, s)) Where (s ~ String, m ~ List), we get (Parses) Where (s ~ String, m ~ Identity), we get (Parser) If we want zero or one parse results, we replace List with Maybe, if we want literate parse errors, then we use Either. All of this hinges off of the initial State Effect.

@ancbi

4 жыл бұрын

@@Dan-gs3kg Hey. Thanks for making it clear. It was my ignorance of StateT making me say what I said.

@Dan-gs3kg

4 жыл бұрын

@@ancbi you're welcome. If you want to look at how "stacked" a parser combinator library gets look for the packages: megaparsec, parser-combinators, and yoctoparsec. The first is a fully featured library that generally dominates in performance, and expressiveness in both passing and error reporting. Yet it operates on the same principle seen previously. The second is a library that can interface with any parser combinator library. This is possible because of the algebraic structure of parser combinators. In other words, those principles are very permissive. And the third is very reductive of what a parser combinator library is. It's effectively a pile of free theorems (invariants) and one primitive: The single token matching primitive. At some point you figure out that a principled outlook is the most constructive.

amazing speaker

Strange instance of applicative where he uses only head of the list

A thousand upvotes! I'm building a simple parser in SCSS of all languages. Let's say it's an interesting adventure. Especially considering that my programming skills are rusty.

Does this kind of parser run in O(n), assuming an unambiguous grammar? n being the length of the input string.

@DutchmanDavid

4 жыл бұрын

I don't think it does, but that's because this is a pretty naive implementation (which is totally fine BTW - that way more people can understand what roughly happens behind the screen). If you want O(n), take a look at a full parser implementation like Parsec, Megaparsec or Attoparsec (just to name a few).

@Lttlemoi

4 жыл бұрын

No. It may have to do a bit of backtracking when the parser should take the second possibility in the sub-parsers. This means re-parsing some stuff, making it non-linear in complexity. For example, consider the simple case "2" and the parser from the video. First, it tries to parse this string as 'term+expr', which expands to 'factor*term+expr' and ultimately '(expr)*term+expr'. The '(expr)' fails, so it tries the second alternative of 'factor', which is 'int'. This succeeds, so it goes back up the tree to parse '*term+expr' out of (2, ""), which fails. Therefore, it tries the second alternative of 'term' in 'term+expr'. This ends up parsing (2, "") again, with '+expr' left over to parse out of the empty string. This again fails, so the second case of the 'expr' parser is used, which eventually succeeds after another round of backtracking in the 'term' and 'factor' parsers to produce the final result: (2, "")

I feel like I need to take a ten week course on this.

@gabe_owner

4 жыл бұрын

I felt that way when I first saw Haskell, too. I've been learning it as a hobby since August and it's totally revitalized my interest in computer science on the whole.

There is a Channel on KZread called low-level-javascript and the guy has a series building a parsing combinator from scratch. It is super interesting and o highly recommend, he's helping me a Lot with my parsing studies

@kartikdeepsagar

Жыл бұрын

Yes that guy is a genious

I wrote a text adventure game in the mid 80's, so I guess the programming that interprets the English commands is a parser :)

@petros_adamopoulos

4 жыл бұрын

It is, but more of a stone tool than this kind of weapon.

Thanks for sharing the link to the library, I will drink a beer now, and try to write my own parser.

can anyone tell me a practical use for parsers? like I watched the entire video and know what they do, but I feel a little unguided, in what common situation you'd use specifically a parser and not just a for loop

@DavidJCobb

4 жыл бұрын

I mean, a parser could be built on a for-loop. Parsing is basically just the process of reading some data, like a mathematical expression, and understanding it. Math expressions can't always be calculated left-to-right (i.e. in the order you or your program would read them), like (1 + 3 * (7 - 1)), so one approach you may take is to decode the expression into objects -- a tree structure -- and then, after you've read and understood the whole expression, you'd use that data to calculate it in the right order. The video's approach is to use functions that are chained in sequence, and those functions could in theory use a for loop. For example, we may have a parser function for variable names, which would want to use a for-loop to read until it sees a character that can't be a variable name. We may have a parser function for whole numbers rather than single digits, which would take the same approach.

@johngibson4874

2 жыл бұрын

Programming language interpreters and compilers. JSON parsers, syntax highlighters, linters, transpilers (like Babel) web browsers that parse html and css, web scrapers all use parsers. Whether the average working programmer uses them is another story. Another example would be if you find yourself making a DSL for adding content to your video game and would rather not write the content in C#, you might consider writing a parser. Anytime you take input and transform it to produce some for of structured output, you are in essence writing or using a parser

@rahzaelfoe3288

5 ай бұрын

According to LangSec, all input should be parsed into a well defined structure (i.e. a type that represents only the set of valid input) before being processed. That way you aren't making assumptions about your input that can be exploited by attackers. The type of parser used should match the complexity of the Grammer used to define valid input, following Chomsky's hierarchy of Grammers.

Idear

@JNCressey

4 жыл бұрын

parzer

It looks like a complex grammar and a carefully crafted example could cause the parser to generate a list of trees exponential in the string length. Which would be very bad.

@Dan-gs3kg

4 жыл бұрын

Either don't return a list of possible results, return a proper stream of possible results, or something else. Eg "Parser a = String -> (a, String)" which only returns the one. The grammar is very literate, though the snag is learning what the combinators mean initially.

List of results? Wouldn't an Either be better? Then you either get the tree, or an error back

Nooo, the list scares me 😭 Why couldn't you just use a normal Maybe

Pleased to observe that he uses the vi editor - a REAL man :-)

@lepidoptera9337

Жыл бұрын

That's not a sign of manhood. It's a sign that he has a clinical case of needing to be different. ;-)

@sebastiangudino9377

7 ай бұрын

​@@lepidoptera9337Yeah, "different". Because he uses the text editor that comes with every computer ever. He is so quirky :/

@lepidoptera9337

7 ай бұрын

@@sebastiangudino9377 It doesn't come with Windows, child. Why would it? Windows has specialized IDEs of all sorts for all kinds of R&D. I am currently using Eclipse with an embedded microcontroller environment. The hardware debugger is fully integrated with the code editor and I can step through my program line by line. I could never do that with vi. OK, now you got your two minutes of attention. I hope your basement has gotten a little warmer. ;-)

@sebastiangudino9377

7 ай бұрын

@@lepidoptera9337 WSL is a POSIX system that comes with windows from Windows 10 onwards. It includes vi

vdisj ::= "either" vp "or" vp ndisj ::= "either" np "or" np "An expression can either be a term plus an expression or a term." Parse error!

Professor Hutton looks like Moby.

Again with the haskell! Why do you keep inviting this guy?!

My parser in php is just a function with string_replace() and preg_replace_callback() in it. I think a parser is pretty easy stuff until you have nested matches.

@rahzaelfoe3288

5 ай бұрын

I'm not going to lie, this seems like a terrible idea. Using repeated string replace is a great way to turn your parser (anything that fills the ROLE of a parser, no matter the mechanism) into a turing machine that treats malformed/malicious input as a turing-complete programming language. I'd recommend looking into the LangSec approach to parsing. The computational power of the automaton you use to parse input should match the complexity of Grammer required to describe the set of valid inputs. No more and no less.

No Tripod?

Using C could to implement a separate lexer, and parser using the shunting yard algorithm for infix expressions is more didactic IMO

@johngibson4874

2 жыл бұрын

You should make a video. I would like to see how it works

Okay, so expr ::= term + expr | term. Right. Now, lets add minus, will we? expr::= term + expr | term - expr | term. Whoops, now what? Oh. And, btw, is the order of operands to significant? How about left recursion?

So Parser is just ReadS?

The tricky part for me is how it knew how to sequence the execution. How is the priority of * over + understood?

@johngibson4874

2 жыл бұрын

It uses recursion. Higher precedence operators appear lower in the stack. It does multiplication before adding because in the grammer and parser multiplication has to be parsed and evaluated before addition. Look up Jack Crenshaw's series Let's Build A Compiler for another explanation. His approach uses recursive descent parsing instead of parser combinators but it is the same idea

I thought I was having a stroke at 1:40!

at the last example, I was expecting to either have something parsed or get the "unconsumed" string... but the result was nothing with nothing "unconsumed"

@iabervon

4 жыл бұрын

It's giving a list of all the ways the input can match an expr with something left over. The last example gives the answer "it can't be an expr with anything left over". In a context where you could have an expr or something else, it would first pass the whole string to the expr parser, then pass the whole string to the other parser; choices remember the original string, and pass that to each parser, rather than passing the unconsumed part to the next parser like sequences do. If the expr parser gave [(nothing,"(2+4")], that would mean it was okay for an expr to consist of nothing.

haskell is so much like black magic lol I should learn it

why this sir doesn't have a single playlist at all? do computerphile forgot to make one? "The functional programming series maybe" ?

Graham Hutton wasn't even born when the early papers on parsing were written. Is this dude even real?????

import argparse

Haskell can be a bit of a 'culture shock' to people like me who are used to procedural programming, but I definitely want to learn more about it.

Thanks

> has got a Mac > codes on Vi

I had to google the pronounciation of parsing. I didn't know that there were words pronounced differently in en-US and en-GB.

@randomizednamme

4 жыл бұрын

There are all kinds of words that are pronounced differently in each dialect

Okay so now let's build this in C

For those interested in funtional parsing in python, check the parsy library.

Is that vim running

@henrituhola

4 жыл бұрын

Terminal + vim & ghci

But can it divide by zero?

Hascal

recursive descent(?)