![]() Just as a regular grammar can be utilized to parse an input string into an output string, a regular expression converts strings quite similarly. Production rules:, ad infinitum.Ī regular grammar is composed of rules like those of Parseltongue.Let’s say that our pretend formal language, Parseltongue, has the following formal grammar: To elucidate this new vocabulary, I’ll walk through an example of converting a set of nonterminals into terminals using a made-up formal grammar. In linguist-speak, a language’s formal grammar provides a framework with which nonterminals (input or intermediate string values) can be converted into terminals (output string values). Grammars provide the rules that build languages. I briefly mentioned that formal grammars are syntactic rules: rules that give all possible valid phrases for a given formal language. Some formal languages have stricter grammars than others, so Chomsky sought to organize formal grammars into his eponymous hierarchy. The Chomsky hierarchy is an ordering of formal grammars - think syntactic rules for formal languages - such that each grammar exists as a proper subset of the grammars above it in the hierarchy. But, before we can understand the jump from Chomsky to regular expressions, I’ll outline the Chomsky hierarchy. Yes, it was this hierarchy that brought regular expressions to computer science. The Chomsky hierarchy transformed the code that computer scientists, software engineers, and hobbyists write today. His contributions to the field of linguistics in particular exemplify the impact of interdisciplinary research on computer science. This affirmed my belief that all fields - even those that appear disparate from computer science - have something to offer to computing and the tech industry. The more I researched Chomsky’s academic work, the more accidental Chomsky’s foray into computing seemed. Because he is so highly regarded in all of these fields, his indirect contributions to the field of computer science often fall by the wayside. Wikipedia christens Noam Chomsky as a linguist, philosopher, cognitive scientist, historian, social critic, and political activist, but not as a computer scientist. To begin, let’s return to Chomsky: what does he have to do with regular expressions? Hell, what does he even have to do with computer science? A Computer Scientist By Accident Though I won’t teach you how to use regular expressions in any particular programming language, I hope that my linguistic introduction will inspire you to dive deeper into how regular expressions work in your programming language of choice. I hope to spellbind you, too, with the linguistics behind regular expressions, a a backstory unknown to most programmers. What enchanted me about regular expressions was the homonymous linguistic concept that powered them. Little did I know that learning about Chomsky would drag me down a rabbit hole back to regular expressions, and then magically cast regular expressions into something that fascinated me. I had to write an essay about a famous computer scientist or academic whose work impacted computer science. I didn’t attend more than a handful of lectures, but one of the assignments stuck with me. The purpose of this course was to draw students who had never written a line of code into CS by introducing them to concepts like cryptography, human-computer interaction, machine learning - you know, only the latest and greatest of tech buzzwords. I expected regular expressions to crop up again in my upper-level computer science coursework - maybe by then I’d finally feel ready to tackle them - but I encountered them in an introductory class that I had put off until my senior year. ![]() ![]() Regular expressions seemed nonsensical, impenetrable. When I first saw a regular expression - often abbreviated as “regex” - I remember feeling dizzy from looking at the litany of parentheses, asterisks, letters, and numbers. Regular expressions inspire fear in new and experienced programmers alike. By Alaina Kafkes Exploring the Linguistics Behind Regular Expressions How a linguistic breakthrough ended up in code Image Credit: xkcd
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |