Algorithms beyond programming

maddog · May 13, 2009

Still, the issue of termination is an important consideration in the definition of algorithm. Otherwise, it would not have been discussed.
Since all books I've used on the subject of algorithms include termination as a part of the algorithm definition I suspect that allowing nonterminating procedures to be part of algorithms makes the definition not useful.
As Minsky pointed out, if you don't know what the answer is, then what do you do.

Consider the embedded code with the modern Microwave. It basically functions until you

turn it off, the power goes out or you find some way to reset it (funny button in the back).

The algorithm here takes each button press and processes it according to some preset set

of rules which were encoded. So any termination here is nonstandard. Yes it is a program also.

As Pyrotex said earlier, Algorithms are often expressed in "psuedo-code". Termination is

not always the focus. Some people restrict algorithms to require an end-state, Not All. :smilingsun:

maddog

maddog · May 13, 2009

To be honest no. It is provable that there is no finite decimal expansion for pi or sqrt(2). So no algorithm can be written that computes these values.

What's wrong with process, procedure, computation, method, technique, method, routine, or operation?

What if I define an "algrorithm" for computing [imath]\pi[/imath] to arbitrary precision.

If I were to set that "precision" to be "exact" and I could continue computing to that

precision, my "algorithm" would terminate.

Periodically it produces output of successive answers. Does this program not ending (if I

choose), make the algorithm that designed it "not an algorithm" ??? :shrug:

This is often the practice at various Scientific Computing Centers around the world that in

their "idle time" they compute Primes. It is useful and it never ends (there is always more

primes). It is the operating system that suspend this task at the end of its time slice

to run other tasks.

Sometime the "answer" is not at the "end of the journey", it is getting there or the "journey"

itself. ;)

maddog

maddog · May 13, 2009

The term parse as you use it Pyrotex is incorrect. To parse is to identify the relationship between the words or parts of a sentence. A parser accepts and rejects input.

The FSM is an automaton that is capable of parsing what are known as linear grammars. These are simple grammars. Push down automatons are required for the next level of grammar complexity called the context free grammars.

I'm not surprised that you have not heard parse used correctly. It rarely is.

Another example of the misuse of language is found in a company where they told people to "solution the problem." No one solved problems there. I always imagined the bosses stirring large vats of liquid trying to create solutions.

I believe that Pyrotex was using the definition of "parse" as similar to that in Wiki

Parsing - Wikipedia, the free encyclopedia

which would be my definition as well.

I was recently using C# code where I was needing to get IP address from a string as

"192.168.13.4". Microsofts DotNet has a neat feature called Parse that will decode this

address into a C# simple type as long.

maddog

stereologist · May 13, 2009

Just because MS also misuses the term parse does not mean anything. MS is notorious for doing things their way. And I am familiar with lots of instances of the misuse of the term parse. And you admit you misuse the term parse and that is par for the course.

stereologist · May 13, 2009

As far as algorithm goes, you mention things such as finding primes. I suggest that each instance of finding a prime is an algorithm. The non-ending loop is not an algorithm.

I also suggest that you be wary of the Wiki. It has no more correctness than this forum.

maddog · May 14, 2009

Just because MS also misuses the term parse does not mean anything. MS is notorious for doing things their way. And I am familiar with lots of instances of the misuse of the term parse. And you admit you misuse the term parse and that is par for the course.

I will agree that MS does far short of the mark as reputable as to correctness of terms and

such.

I admitted to "misuse" of the term "parse" ? When.

Aren't we talking "context" here... :huh:

maddog

maddog · May 14, 2009

As far as algorithm goes, you mention things such as finding primes. I suggest that each instance of finding a prime is an algorithm. The non-ending loop is not an algorithm.

I also suggest that you be wary of the Wiki. It has no more correctness than this forum.

The whole enchilada can be an algorithm. As more precision is required the algorithm

fine tunes itself to the higher order primes. To chop it up into individual prime search

would make it only a piece of the puzzle. Typically an algorithm needs no input values;

only a goal to achieve. Your method would require too many input values for each value

to be computed in "their own" algorithm.

BTW, what are your credentials regarding words such as "parse" & "algorithm".

I can take a definition from Websters or Dictionary.com are would they not be "good

enough" for you.... :huh:

maddog

maddog · May 14, 2009

Here are the results of "parse"

from Dictionary.com:

parse

/pɑrs, pɑrz/ Show Spelled Pronunciation [pahrs, pahrz] Show IPA verb, parsed, pars⋅ing. –verb (used with object) 1. to analyze (a sentence) in terms of grammatical constituents, identifying the parts of speech, syntactic relations, etc. 2. to describe (a word in a sentence) grammatically, identifying the part of speech, inflectional form, syntactic function, etc. 3. Computers. to analyze (a string of characters) in order to associate groups of characters with the syntactic units of the underlying grammar.

–verb (used without object) 4. to admit of being parsed.

Origin:

1545–55; < L pars part, as in pars ōrātiōnis part of speech

Related forms:

pars⋅a⋅ble, adjective

parser, noun

Dictionary.com Unabridged

Based on the Random House Dictionary, © Random House, Inc. 2009.

Cite This Source |

Link To parse

parse (pärs)

v. parsed, pars·ing, pars·es

v. tr.

To break (a sentence) down into its component parts of speech with an explanation of the form, function, and syntactical relationship of each part.
To describe (a word) by stating its part of speech, form, and syntactical relationships in a sentence.
2. To examine closely or subject to detailed analysis, especially by breaking up into components: "What are we missing by parsing the behavior of chimpanzees into the conventional categories recognized largely from our own behavior?" (Stephen Jay Gould).
3. To make sense of; comprehend: I simply couldn't parse what you just said.

[*]Computer Science To analyze or separate (input, for example) into more easily processed components.

v. intr.

To admit of being parsed: sentences that do not parse easily.

[Probably from Middle English pars, part of speech, from Latin pars (ōrātiōnis), part (of speech); see perə-2 in Indo-European roots.]

pars'er n.

The American Heritage® Dictionary of the English Language, Fourth Edition

Cite This Source

Parse

Parse, v. t. [imp. & p. p. Parsed; p. pr. & vb. n. Parsing.] [L. pars a part; pars orationis a part of speech. See Part, n.] (Gram.) To resolve into its elements, as a sentence, pointing out the several parts of speech, and their relation to each other by government or agreement; to analyze and describe grammatically. Let him construe the letter into English, and parse it over perfectly. --Ascham.

Cite This Source

#newimg{ background-image:url('http://sp.ask.com/en/i/dictionary/translate_new.png'); margin-top:8px; } #newimg6{ filter:progid:DXImageTransform.Microsoft.AlphaImageLoader(src='http://sp.ask.com/en/i/dictionary/translate_new.png', sizingMethod='crop'); } parse

[from linguistic terminology] vt.

1. To determine the syntactic structure of a sentence or other utterance (close to the standard English meaning). "That was the one I saw you." "I can't parse that."

2. More generally, to understand or comprehend. "It's very simple; you just kretch the glims and then aos the zotz." "I can't parse that."

3. Of fish, to have to remove the bones yourself. "I object to parsing fish", means "I don't want to get a whole fish, but a sliced one is okay". A `parsed fish' has been deboned. There is some controversy over whether `unparsed' should mean `bony', or also mean `deboned'.

Jargon File 4.2.0

Cite This Source

parse

c.1553, "to state the parts of speech in a sentence," verb use of M.E. pars (n.) "part of speech" (c.1300), from O.Fr. pars, pl. of part "part," from L. pars (see part (n.)) in school question, Quae pars orationis? "What part of speech?"

Cite This Source

/*styles applied for IE6 and IE7*/ .linkpage{ font-family:verdana; font-size:12px; color:#333333; padding-bottom:5px; margin-top:5px; } .linkdiv1{ padding-bottom:14px; padding-top:5px; }

From Reference.com:

parsing

In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a sequence of tokens to determine their grammatical structure with respect to a given (more or less) formal grammar.

Parsing is also an earlier term for the diagramming of sentences of natural languages, and is still used for the diagramming of inflected languages, such as the Romance languages or Latin. The term parsing comes from Latin pars (ōrātiōnis), meaning part (of speech).

Parser

A parser is one of the components in an interpreter or compiler, which checks for correct syntax and builds a data structure (often some kind of parse tree, abstract syntax tree or other hierarchical structure) implicit in the input tokens. The parser often uses a separate lexical analyser to create tokens from the sequence of input characters. Parsers may be programmed by hand or may be semi-automatically generated (in some programming language) by a tool (such as Yacc) from a grammar written in Backus-Naur form. Human languages

In some machine translation and natural language processing systems, human languages are parsed by computer programs. Human sentences are not easily parsed by programs, as there is substantial ambiguity in the structure of human language. In order to parse natural language data, researchers must first agree on the grammar to be used. The choice of syntax is affected by both linguistic and computational concerns; for instance some parsing systems use lexical functional grammar, but in general, parsing for grammars of this type is known to be NP-complete. Head-driven phrase structure grammar is another linguistic formalism which has been popular in the parsing community, but other research efforts have focused on less complex formalisms such as the one used in the Penn Treebank. Shallow parsing aims to find only the boundaries of major constituents such as noun phrases. Another popular strategy for avoiding linguistic controversy is dependency grammar parsing.

Most modern parsers are at least partly statistical; that is, they rely on a corpus of training data which has already been annotated (parsed by hand). This approach allows the system to gather information about the frequency with which various constructions occur in specific contexts. (See machine learning.) Approaches which have been used include straightforward PCFGs (probabilistic context free grammars), maximum entropy, and neural nets. Most of the more successful systems use lexical statistics (that is, they consider the identities of the words involved, as well as their part of speech). However such systems are vulnerable to overfitting and require some kind of smoothing to be effective.

Parsing algorithms for natural language cannot rely on the grammar having 'nice' properties as with manually-designed grammars for programming languages. As mentioned earlier some grammar formalisms are very computationally difficult to parse; in general, even if the desired structure is not context-free, some kind of context-free approximation to the grammar is used to perform a first pass. Algorithms which use context-free grammars often rely on some variant of the CKY algorithm, usually with some heuristic to prune away unlikely analyses to save time. (See chart parsing.) However some systems trade speed for accuracy using, eg, linear-time versions of the shift-reduce algorithm. A somewhat recent development has been parse reranking in which the parser proposes some large number of analyses, and a more complex system selects the best option.

Programming languages

The most common use of a parser is as a component of a compiler or interpreter. This parses the source code of a computer programming language to create some form of internal representation. Programming languages tend to be specified in terms of a context-free grammar because fast and efficient parsers can be written for them. Parsers are written by hand or generated by parser generators.

Context-free grammars are limited in the extent to which they can express all of the requirements of a language. Informally, the reason is that the memory of such a language is limited. The grammar cannot remember the presence of a construct over an arbitrarily long input; this is necessary for a language in which, for example, a name must be declared before it may be referenced. More powerful grammars that can express this constraint, however, cannot be parsed efficiently. Thus, it is a common strategy to create a relaxed parser for a context-free grammar which accepts a superset of the desired language constructs (that is, it accepts some invalid constructs); later, the unwanted constructs can be filtered out.

Overview of process

The following example demonstrates the common case of parsing a computer language with two levels of grammar: lexical and syntactic.

The first stage is the token generation, or lexical analysis, by which the input character stream is split into meaningful symbols defined by a grammar of regular expressions. For example, a calculator program would look at an input such as "12*(3+4)^2" and split it into the tokens 12, *, (, 3, +, 4, ), ^, and 2, each of which is a meaningful symbol in the context of an arithmetic expression. The parser would contain rules to tell it that the characters *, +, ^, ( and ) mark the start of a new token, so meaningless tokens like "12*" or "(3" will not be generated.

The next stage is parsing or syntactic analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to a context-free grammar which recursively defines components that can make up an expression and the order in which they must appear. However, not all rules defining programming languages can be expressed by context-free grammars alone, for example type validity and proper declaration of identifiers. These rules can be formally expressed with attribute grammars.

The final phase is semantic parsing or analysis, which is working out the implications of the expression just validated and taking the appropriate action. In the case of a calculator or interpreter, the action is to evaluate the expression or program; a compiler, on the other hand, would generate some kind of code. Attribute grammars can also be used to define these actions.

Types of parsers

The task of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar. This can be done in essentially two ways:

Top-down parsing - Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for parse trees using a top-down expansion of the given formal grammar rules. Tokens are consumed from left to right. Inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules . LL parsers and recursive-descent parser are examples of top-down parsers, which cannot accommodate left recursive productions. Although it has been believed that simple implementations of top-down parsing cannot accommodate direct and indirect left-recursion and may require exponential time and space complexity while parsing ambiguous context-free grammars, more sophisticated algorithm for top-down parsing have been created by Frost, Hafiz, and Callaghan which accommodates ambiguity and left recursion in polynomial time and which generates polynomial-size representations of the potentially-exponential number of parse trees. Their algorithm is able to produce both left-most and right-most derivations of an input with regard to a given CFG.
Bottom-up parsing - A parser can start with the input and attempt to rewrite it to the start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. LR parsers are examples of bottom-up parsers. Another term used for this type of parser is Shift-Reduce parsing.

Another important distinction is whether the parser generates a leftmost derivation or a rightmost derivation (see context-free grammar). LL parsers will generate a leftmost derivation and LR parsers will generate a rightmost derivation (although usually in reverse) .

Examples of parsers

Top-down parsers

Some of the parsers that use top-down parsing include:

Recursive descent parser
LL parser (Left-to-right, Leftmost derivation)
X-SAIGA - eXecutable SpecificAtIons of GrAmmars. Contains publications related to top-down parsing algorithm that supports left-recursion and ambiguity in polynomial time and space.

Bottom-up parsers

Some of the parsers that use bottom-up parsing include:

Precedence parser
- Operator-precedence parser
- Simple precedence parser
[*] BC (bounded context) parsing
[*] LR parser (Left-to-right, Rightmost derivation)
[*] CYK parser

Parser development software

Some of the well known parser development tools include the following. Also see comparison of parser generators.

See also

Generating strings

Parsing concepts

References

Further reading

Parsing Techniques - A Practical Guide web page of book includes downloadable pdf.

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 29, 2008 at 00:32:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

.hbpad { margin-top:0px; } .result_copyright { } Parse Definition

What Is Parse? Find Out w/the Dictionary Toolbar

Sponsored Results www.ScienceOps.com

algorithm

Procedure that produces the answer to a question or the solution to a problem in a finite number of steps. An algorithm that produces a yes or no answer is called a decision procedure; one that leads to a solution is a computation procedure. A mathematical formula and the instructions in a computer program are examples of algorithms. Euclid's Elements (circa 300 BC) contained an algorithm for finding the greatest common divisor of two integers. Manipulation of lists (searching for, inserting, and removing items) can be done efficiently by using algorithms.

Learn more about algorithm with a free trial on Britannica.com.

Encyclopedia Britannica, 2008. Encyclopedia Britannica Online.

.moreLink { color:#52850F; } algorithm

Jan 01, 2004; algorithm A prescribed set of well-defined rules or instructions for the solution of a problem, such as the performance of a...

Read more with a free trial on HighBeam.com »

Algorithm

Jan 01, 2003; Algorithm An algorithm is any well-defined procedure for solving a given class of problems. Ideally, when applied to a particular...

Read more with a free trial on HighBeam.com »

An approximate cone beam reconstruction algorithm for gantry-tilted CT using tangential filtering.(computed tomography)

Jan 01, 2006; FDK algorithm is a well-known 3D (three-dimensional) approximate algorithm for CT (computed tomography) image reconstruction and...

Read more with a free trial on HighBeam.com »

To propose an algorithm for team forming: simulated annealing K team-forming algorithm for heterogeneous grouping.

Mar 22, 2005; INTRODUCTION This algorithm was revised from K team-forming algorithm (2), which similar to K Means clustering algorithm (1), and...

Read more with a free trial on HighBeam.com »

Algorithm Trading Solutions Unveils TRACER, its Eighth Proprietary Algorithm.

Mar 31, 2005; NEWARK, N.J. -- Algorithm Trading Solutions, a division of TradeTrek Securities, LLC, an institutional broker-dealer specializing...

Read more with a free trial on HighBeam.com »

========================================================

I do hope this clarifies. :huh:

maddog

stereologist · May 14, 2009

Sorry I thought you realized that you were misusing the term parse. Most people are unaware that they do.

LaurieAG · May 15, 2009

Good one Maddog,

My sentiments exactly, lol.

stereologist · May 15, 2009

Well done maddog. I see that the definitions you provide for parsing show how that programmers almost always use the term incorrectly. Well done.

stereologist · May 15, 2009

And the definitions you provide for algorithm all involve the termination requirement.

Again well done.

Qfwfq · May 15, 2009

Can't believe it! :surprise: I must disagree with Buffy on matters of this kind!

Seems obvious to me that parsing includes lexing, which is recognizing the tokens. Full parsing would also comprise sorting out syntax, even if only checking it to be well-formed.

All algorithms must halt.
[imath]\pi[/imath] is a transcendental number that has no end.
Ergo, there are no algorithms for computing [imath]\pi[/imath]

But there can be an algorithm to compute it to within a chosen precision. Without this caveat, the problem actually doesn't have a solution, it is self contradictory, for the simple reason that it proposes to write [imath]\pi[/imath] as if it were a rational number although it isn't.

As I've always known it, an algorithm is a <placedescriptionhere> that arrives at a certainly valid solution (for some cases add "or gives up") in a finite number of steps. Quantitatively, valid may mean within a set precision (e. g. long division or iterative methods such as Newton's). A heuristic is a criterion (which might be constructed according the same description) which rejects candidate solutions that certainly are not valid, also in finite time; this term has come to be used with plenty of laxity though. Strictly, a heuristic is something that can be very advantageous (even necessary) to apply before any algorithms, or whatever method for finding actual solutions. Strictly, a heuristic is not an algorithm but, in practice, many of them are called such because of the same description in terms of steps. Methods for attempting to find a factor of a given number, used for rejecting them in prime searching, should more properly be called heuristics. Due to the fact that, in many cases, suitable heuristics are deemed sufficient for practical purposes, many folks attribute the term the "not quite right but that'll do" sort of a meaning (as would seem according to wikipedia).

It is just that Buffy's example in
post #9 constitutes an algorithm by even your definition with the last statement in
essence
"got to step 1" or repeat.
This is in a sense a terminating case that just starts over.

A program can contain an algorithm without being one.

Just like an algorithm needn't be a computer program, not all programs are algorithms. A program which repeats something, even an algorithm, at every request until given a quit command or killed, is not an algorithm.

while(true)fork(); :computerkick:

stereologist · May 15, 2009

Seems obvious to me that parsing includes lexing

I would disagree here Qfwfq. Parsing has a requirement for determining the relationships between the syntactical elements.

One of the definitions says, "syntactical relationship of each part". It is this part of the definition that leaves out lexing. The word "lexing" of course is a contraction of lexical analysis. I prefer the word scanning, since that is closer to what is being done. The scanning process involves searching for something of interest. Usually scanning is used to do simple tasks such as locate telephone numbers, zip codes, or email addresses.

Technically, a parser is a program that parses. A parser must accept or reject the input as a sentence of the target grammar. A parser does not transform the input into another form. That is done by a transducer.

Qfwfq · May 16, 2009

I would disagree here Qfwfq. Parsing has a requirement for determining the relationships between the syntactical elements.

errrrrrgh, sorry to say but I think you did not understand what I wrote.

Perhaps you would replace my word includes with "requires having been done" but uncouth slobs like me tend to see lexing as being part of it, rather than "before" it.

Further, I did not mean that compilers, interpreters and the like are parsers, but their activity definitely includes parsing (and lexing). Just as parsing is quite intertwined with whatever is done with the result (except the trivial accept or reject case), so is lexing quite intertwined with parsing. Unlike the compile-link sequence (and even preprocessor-compiler), it would not be practical to make the compiler as a suite of three separate operations; although it is definitely possible to design the lexing to output a format in which tokens are all simple, as ready as possible for the bare parser, it strikes me somewhat less feasible between the parser and compiler stages. Seems the "parser only" would wind up actually being a compiler to some intermediate language (along the lines of the .NET framework for instance).

maddog · May 20, 2009

Well done maddog. I see that the definitions you provide for parsing show how that programmers almost always use the term incorrectly. Well done.

Not the answer from you I expected... :naughty:

Borrowed from my post#42 above ...

Here are the results of "parse" ... [abridge]

From Reference.com:
parsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a sequence of tokens to determine their grammatical structure with respect to a given (more or less) formal grammar.
...
A parser is one of the components in an interpreter or compiler, which checks for correct syntax and builds a data structure (often some kind of parse tree, abstract syntax tree or other hierarchical structure) implicit in the input tokens. The parser often uses a separate lexical analyser to create tokens from the sequence of input characters. Parsers may be programmed by hand or may be semi-automatically generated (in some programming language) by a tool (such as Yacc) from a grammar written in Backus-Naur form. Human languages

In some machine translation and natural language processing systems, human languages are parsed by computer programs. Human sentences are not easily parsed by programs, as there is substantial ambiguity in the structure of human language. In order to parse natural language data, researchers must first agree on the grammar to be used. The choice of syntax is affected by both linguistic and computational concerns; for instance some parsing systems use lexical functional grammar, but in general, parsing for grammars of this type is known to be NP-complete. Head-driven phrase structure grammar is another linguistic formalism which has been popular in the parsing community, but other research efforts have focused on less complex formalisms such as the one used in the Penn Treebank. Shallow parsing aims to find only the boundaries of major constituents such as noun phrases. Another popular strategy for avoiding linguistic controversy is dependency grammar parsing.
Most modern parsers are at least partly statistical; that is, they rely on a corpus of training data which has already been annotated (parsed by hand). This approach allows the system to gather information about the frequency with which various constructions occur in specific contexts. (See machine learning.) Approaches which have been used include straightforward PCFGs (probabilistic context free grammars), maximum entropy, and neural nets. Most of the more successful systems use lexical statistics (that is, they consider the identities of the words involved, as well as their part of speech). However such systems are vulnerable to overfitting and require some kind of smoothing to be effective.
Parsing algorithms for natural language cannot rely on the grammar having 'nice' properties as with manually-designed grammars for programming languages. As mentioned earlier some grammar formalisms are very computationally difficult to parse; in general, even if the desired structure is not context-free, some kind of context-free approximation to the grammar is used to perform a first pass. Algorithms which use context-free grammars often rely on some variant of the CKY algorithm, usually with some heuristic to prune away unlikely analyses to save time. (See chart parsing.) However some systems trade speed for accuracy using, eg, linear-time versions of the shift-reduce algorithm. A somewhat recent development has been parse reranking in which the parser proposes some large number of analyses, and a more complex system selects the best option.
Programming languages

The most common use of a parser is as a component of a compiler or interpreter.
...

Hightlighting just the comments in Green I think get at what I am saying which from I can

tell is Not what you are saying.

As Qfwfq has said above Compilers & Interpreters have a Parser nor are ones!

In this example of some text --> "192.168.172.13" is a dotted decimal IP address.

I would parse it (removing the ".") to arrive at the number 25251853. This is parsing. I

will not accept it to be not. Period. :) :shrug:

maddog

Sign In

Algorithms beyond programming

Recommended Posts

Link to comment

Share on other sites

Top Posters In This Topic

Popular Days

Top Posters In This Topic

Popular Days

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation