There was a very interesting and wide-reaching question on the forums
about the uses of lexical analysis and regular expressions
and this general sort of string processing outside of what we're doing in this class.
The essence of the question was, what else is this good for in the real world?
Is it used to do anything interesting?
And the question is actually a resounding yes.
There are a large number of great uses of regular expressions and lexical analysis
beyond just building web browsers or writing language interpreters.
One of the most basic is in electronic commerce.
I hinted at this in the beginning of Unit 1,
but things like phone numbers and credit card numbers are recognized
and processed using regular expressions--
essentially using lexical analysis.
Break down a big input string from the user into something that you want to deal with.
For example, users often enter their phone numbers or credit card numbers
with hyphens in the middle, but maybe you want to get rid of all of the hyphens
so that you can just treat it as one big number and ask about it in your database.
However, quite a few other things make use of lexical analysis.
Let me give you one you probably haven't thought of: virus detection.
These days there are a number of adversaries out there in the world of computing--
people who are interested in taking over your machine remotely,
perhaps for economic reasons.
Maybe they'd like to take over your machine and use it to send spam
or do something else malicious--delete your files, something fun like that.
It turns out that the virus software you probably have running on your computer now--
that is, the antivirus software, the good stuff designed to keep away the evil attackers--
is based on regular expressions and lexing.
In essence, in order to be relatively interesting,
a virus typically has to have some sort of important payload,
a part where it replicates and takes over another program,
writing out something to the disk or changing data structures in memory.
A virus definition file, which you may have seen your antivirus software talk about updating,
is actually just a big list of tokens.
For every virus out there, we write a regular expression
corresponding to the machine code,
corresponding to this payload that it uses to take over or infect other files.
And a virus scanner is actually just like a lexer
except that if you match any of those tokens, it's a bad scene.
A virus scanner runs all of those finite state machines over executable programs
before you run them or attachments you download from the Internet.
And if they find any of those patterns, they stop and say,
"Oh, I think this file may be malicious. Let's do something special with it."
So virus scanning or virus checking also uses regular expressions.
Here's a third use.
String matching in general is commonly used for dealing with computational biology
like DNA sequencing or protein folding.
When we get pieces of DNA from biological laboratories,
you can view human DNA or animal DNA in the world
as basically just a long string over a very simple alphabet of 4 characters--G, C, A, T--
corresponding to special objects or special structures
in the world of biology and biochemistry.
And everything about us, we believe, in the physical world
is based on the interactions or the unrolling or instructions gleaned from DNA,
perhaps through DNA or RNA transcription.
I'm not much of a biologist, but I know that these days a lot of biology research
is done with the aid of or enabled by computers.
So for example, if I want to check to see if 2 particular DNA sources
have a relatively high overlap but when they come out of the biology lab
these strings are a bit scrambled because they've gone through a physical process,
what I essentially want to do is say, "Oh, could this blob of text over here
"match up with this DNA text from some other person?"
"Can I find the best matching or the best alignment?"
And that task uses exactly the same sort of lexical analysis string matching
that we've talked about here.
But I can take it 1 step further.
You might have wondered at some point, "How do we come up with new drugs?"
"How do I make a better aspirin? How does that sort of thing go?"
And while there are definitely in-lab scientific techniques involved--
you might imagine, "Oh, maybe I take some sort of test subject,
"I inject them with my candidate medicine and see if they get better"--
that sort of trial is very expensive.
It would be really nice if we could use mathematical models
to help narrow down the search space
to help get an idea for how drugs might interact in your body, how they might behave.
And it turns out that a lot of chemical interactions at that level
are governed by protein folding--
how various proteins will sort of rub against each other and interact or not.
We can use computers to simulate protein folding
and thus get a better handle on candidate drugs we're designing.
Maybe we can use the computers to simulate a bunch of possibilities,
come up with the best 10, present those to the scientists,
and then those are the ones that we try on live subjects.
That sort of protein folding experiment involves a number of the same sort of techniques
that we're learning about here in lexing--
go over strings, do comparisons, do big simulations.
And in fact, if you're curious about this sort of genome sequence alignment,
string matching, protein folding sort of world,
you might want to check out BLAST--B-L-A-S-T, all capital letters--
which is a common software project for doing just that.
It's not necessarily the fastest, but it is one of the most popular.
And then the final thing I would mention is there are a lot of very high level
readability metrics, both for software and also for natural language text,
that are based on the sort of lexing or lexical analysis or token definition principles
that we've come to know.
For example, one of the least expensive ways of figuring out
the appropriate grade level for a book
is to measure very simple things like the number of words in a sentence
and the number of syllables per word.
Then through some division and multiplication you can arrive at
whether that should be given to a 10-year-old child or a 14-year-old child or whatnot
to read based on expected reading norms.
That sort of readability metric can be easily computed
using exactly the sort of break a string up into words kind of lexical analysis
that we've been focusing on.
And that segues into the final part of this question.
Students were asking about natural language processing.
With the lexing and parsing, the lexical analysis and syntactical analysis
that we'll cover in this class, do they carry over to parsing real-world languages
like Japanese or English or German?
And the answer is, to some degree, yes.
Linguists or computation linguists are often interested
in modeling real-world natural languages
using the same sorts of formal grammars that we're going to introduce in Unit 3.
Stay tuned. Fun stuff.
And this question of breaking a sentence up into words is legitimately tricky
in languages other than English.
I hinted at this in some of the lecture material.
But in languages like Japanese or in Latin where spaces might not be written explicitly,
we really have to think hard about how to break down an utterance into its substructures.
However, natural language processing is actually, in some sense, significantly harder
than the unnatural language processing that we do here.
Real-world languages like English are not well behaved compared to JavaScript.
JavaScript is very artificial, it's very regular.
We know just how it will go, what the nouns are and what the verbs are.
In a language like English, that's very hard to figure out.
So natural language processing is currently, to some degree, still in its infancy.
There are still a lot of tests or a lot of tasks that we would like to be able to carry out
on natural language that are hard to do.
If you're interested in natural language processing, writing computer programs
that look at human written documents and do something with them,
a common task to start with is document summarization.
For example, you might go to a news aggregator site on the Web
and there's a really long article.
Wouldn't it be nice if you could say something like, "Summarize this for me."
"What's the gist of this? Boil it down to just a few sentences."
That's one of the common tasks that natural language processing researchers try to solve.
And it turns out that that task is very difficult.
Sort of a straw algorithm, a cheap way to do it
might be to just take the topic sentence from each paragraph
and put them together, counting on the human who wrote it
to have used a special structure where each paragraph
is introduced by a declarative topic sentence.
It turns out that that simple approach is actually relatively hard to beat
because understanding natural language requires your computer program to have,
in some sense, a model of semantic meaning or the rest of the world.
People will sometimes jokingly say that natural language processing
is AI-complete where complete has a special mathematical meaning.
We may get to deal with jokes and puns like that in a later class on theory.
Suffice it to say for now, to some degree, I'm actually glad
that I work in the easy world of unnatural language processing.
It's significantly harder to deal with the utterances we use day to day
when talking to other people.