Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.soft-sys.math.mathematica > #2698 > unrolled thread

Again : Is there a BNF for Mathematica?

Back to article view | Back to comp.soft-sys.math.mathematica

Contents

  Again : Is there a BNF for Mathematica? "E. Martin-Serrano" <eMartinSerrano@telefonica.net> - 2011-05-25 09:57 +0000
    Re: Again : Is there a BNF for Mathematica? David Bailey <dave@removedbailey.co.uk> - 2011-05-25 23:33 +0000
    Re: Again : Is there a BNF for Mathematica? Richard Fateman <fateman@cs.berkeley.edu> - 2011-06-22 07:44 +0000
    Re: Again : Is there a BNF for Mathematica? Szabolcs Horvát <szhorvat@gmail.com> - 2011-06-22 11:29 +0000
      Re: Again : Is there a BNF for Mathematica? Richard Fateman <fateman@cs.berkeley.edu> - 2011-06-23 11:34 +0000
    Re: Again : Is there a BNF for Mathematica? "E. Martin-Serrano" <eMartinSerrano@telefonica.net> - 2011-06-24 11:44 +0000

#2698 — Again : Is there a BNF for Mathematica?

On 2009 Murray Eisenberg posted the article linked below

  

http://forums.wolfram.com/mathgroup/archive/2009/Apr/msg00232.html



In which he wrote:



>>It's not at all clear to me that a BNF would be of any great 
use for Mathematica : after all, "everything is an expression" and so if 
you avoid any of the "special input forms" such as =, :=, /@, {}, =
[[]], >>etc., along with prefix, infix, and postfix special forms, then 
the grammar is utterly simple.



>>The complexities arise from (1) Attributes, such as Hold, which do not 
explicitly appear as part of the syntax one uses in entering expressions 
but affect the evaluation; and (2) the special input >>forms, where you 
have to begin worrying about order of precedence.



My point now is:



Would the Murray's remark be still valid  if  we talk about a 
BNF grammar whose purpose is to write a parser to make available  just  
the expressions of the form  ( symbol := expression =E2=94=82 symbol 
= expression ) after discarding all the stuff on attributes and 
evaluation order? I am still  concerned, as I posted a year ago o so,  
with the =E2=80=98data dependency graph=E2=80=99  or =E2=80=98what we 
could call  =E2=80=98data dependency part of the parsing tree=E2=80=99.



The underlying idea is to extract all the assignments (left and right 
sides)  in the code preventing the evaluation of the right hand sides. 
Wrapping the right hand sides in assignments  with 
=E2=80=98hold=E2=80=99  is unacceptable for my purpose and need.



Counting on a BNF (affix)  Grammar, a simple way to extract the data 
dependency tree/graph would go like this:



1)      Save in plain text format the piece of code (in a notebook) that 
one needs to parse (all hidden code corresponding to the notebook 
interface would be dropped).



2)      Perform a first parsing step to drop all the elements mentioned 
or referenced by Murray (Hold and controls of order evaluation), leaving 
only the code corresponding to assignments and function definitions.



3)      Perform a second parsing step on the plain text obtained in the  
previous step, which will produce a set of assignments regardless they 
are delayed assignments or not.



Maybe my ideas were clearer if I compare the above procedure with 
another, perhaps equivalent (?), method;  consisting in performing a 
separate (or concurrent) recursive descendent parsing on  all  
{DownValues, UpValues, OwnValues} for the symbols  in the piece of code 
we are interested in. In which case, the parsing trees got in each 
separate step  {DownValues, UpValues, OwnValues} will defined some valid 
form of data dependency graph for the whole piece of code.



Then, with, say, Combinatorica, we would be able to explore and find 
important properties of the parsed code, easing up the task of: 1) 
Speeding up complex and tricky dynamic programs,  2) rewriting programs 
written in older (sometimes very old) Mathematica versions, and, 3) no 
less important, writing the final version of experimental programs 
written incrementally,  with step by step incremented  functionality,  
which typically result in something nearly unreadable.



Regards



E. Martin-Serrano

[toc] | [next] | [standalone]

#2714

On 25/05/2011 10:57, E. Martin-Serrano wrote:
> On 2009 Murray Eisenberg posted the article linked below
>
>
>
> http://forums.wolfram.com/mathgroup/archive/2009/Apr/msg00232.html
>
>
>
> In which he wrote:
>
>
>
>>> It's not at all clear to me that a BNF would be of any great
> use for Mathematica : after all, "everything is an expression" and so if
> you avoid any of the "special input forms" such as =, :=, /@, {}, =
> [[]],>>etc., along with prefix, infix, and postfix special forms, then
> the grammar is utterly simple.
>
>
>
>>> The complexities arise from (1) Attributes, such as Hold, which do not
> explicitly appear as part of the syntax one uses in entering expressions
> but affect the evaluation; and (2) the special input>>forms, where you
> have to begin worrying about order of precedence.
>
>
>
> My point now is:
>
>
>
> Would the Murray's remark be still valid  if  we talk about a
> BNF grammar whose purpose is to write a parser to make available  just
> the expressions of the form  ( symbol := expression =E2=94=82 symbol
> = expression ) after discarding all the stuff on attributes and
> evaluation order? I am still  concerned, as I posted a year ago o so,
> with the =E2=80=98data dependency graph=E2=80=99  or =E2=80=98what we
> could call  =E2=80=98data dependency part of the parsing tree=E2=80=99.
>
>
>
> The underlying idea is to extract all the assignments (left and right
> sides)  in the code preventing the evaluation of the right hand sides.
> Wrapping the right hand sides in assignments  with
> =E2=80=98hold=E2=80=99  is unacceptable for my purpose and need.
>
>
>
> Counting on a BNF (affix)  Grammar, a simple way to extract the data
> dependency tree/graph would go like this:
>
>
>
> 1)      Save in plain text format the piece of code (in a notebook) that
> one needs to parse (all hidden code corresponding to the notebook
> interface would be dropped).
>
>
>
> 2)      Perform a first parsing step to drop all the elements mentioned
> or referenced by Murray (Hold and controls of order evaluation), leaving
> only the code corresponding to assignments and function definitions.
>
>
>
> 3)      Perform a second parsing step on the plain text obtained in the
> previous step, which will produce a set of assignments regardless they
> are delayed assignments or not.
>
>
>
> Maybe my ideas were clearer if I compare the above procedure with
> another, perhaps equivalent (?), method;  consisting in performing a
> separate (or concurrent) recursive descendent parsing on  all
> {DownValues, UpValues, OwnValues} for the symbols  in the piece of code
> we are interested in. In which case, the parsing trees got in each
> separate step  {DownValues, UpValues, OwnValues} will defined some valid
> form of data dependency graph for the whole piece of code.
>
>
>
> Then, with, say, Combinatorica, we would be able to explore and find
> important properties of the parsed code, easing up the task of: 1)
> Speeding up complex and tricky dynamic programs,  2) rewriting programs
> written in older (sometimes very old) Mathematica versions, and, 3) no
> less important, writing the final version of experimental programs
> written incrementally,  with step by step incremented  functionality,
> which typically result in something nearly unreadable.
>
Unfortunately your message has been somewhat garbled by pasting UNICODE 
characters into your message.

I do agree with Murray, in the sense that all the interesting issues 
would be not really syntactic. For example, there is no end of fun to be 
had with MakeBoxes and MakeExpression.

I am very unclear what it is that you yourself really want to do. Do you 
want to write a code analyser of some sort?

I wrote a little debugger package (available from my website) that 
starts from the BoxForm's that you can see if you open a notebook with a 
text editor, or use NotebookGet on a notebook. This isn't a bad way to 
manipulate Mathematica code, because the parsing into boxes has already 
been done.

I'd say, re-writing code to improve its performance or readability is a 
job for a human, not a program. There are so many issues - such as the 
packed array issue - that are not syntactic.

David Bailey
http://www.dbaileyconsultancy.co.uk

[toc] | [prev] | [next] | [standalone]

#3232

On 5/25/2011 2:57 AM, E. Martin-Serrano wrote:
  ... stuff about parsing ...

1. BNF can be used to describe a context-free language.
2. The Mathematica language is not context free, and thus cannot be 
described completely in BNF.
3. If you need to parse Mathematica expressions and you have a 
Mathematica system around, you can simply use it to convert the 
expressions to FullForm, which is easily re-parsed (and does have a BNF).

4. If you do not have a Mathematica around, there are (free) programs 
that will parse Mathematica into something equivalent to FullForm.

5. Your ideas about what you would do if you had a BNF for Mathematica 
seem to conflate syntax with semantics (evaluation) and, so far as I can 
tell, do not seem to make sense.  If you wish to do experiments with 
programming language transformations, you can easily learn about other 
programming languages that are (a) well-defined (b) much more popular 
(c) can be described by BNF (d) are susceptible to transformations into 
the same language for efficiency or readability or program proofs or 
other purposes.

There is a substantial literature on such subjects. I suspect that 
Mathematica has little or nothing to add to the discussion, and in my 
opinion certainly does not have enough value added to compensate for its 
complexity syntactically or semantically. For example, do you think that 
you fully understand the matching process at the core of the rule-based 
transformation system that underlies Mathematica evaluation?
Can you really demonstrate that two non-trivial Mathematica "programs" 
compute the same thing?


RJF

[toc] | [prev] | [next] | [standalone]

#3244

If you are looking to implement a Mathematica parser yourself, you might 
want to look at some earlier efforts first:

http://omath.org/w/index.php?title=Main_Page#Developers
http://stackoverflow.com/questions/1608380/parser-for-the-mathematica-syntax
http://www.mathics.org/

These pages contain links to several other projects (most dead by now).

On 2011.05.25. 11:57, E. Martin-Serrano wrote:
> On 2009 Murray Eisenberg posted the article linked below
>
>
>
> http://forums.wolfram.com/mathgroup/archive/2009/Apr/msg00232.html
>
>
>
> In which he wrote:
>
>
>
>>> It's not at all clear to me that a BNF would be of any great
> use for Mathematica : after all, "everything is an expression" and so if
> you avoid any of the "special input forms" such as =, :=, /@, {}, =
> [[]],>>etc., along with prefix, infix, and postfix special forms, then
> the grammar is utterly simple.
>
>
>
>>> The complexities arise from (1) Attributes, such as Hold, which do not
> explicitly appear as part of the syntax one uses in entering expressions
> but affect the evaluation; and (2) the special input>>forms, where you
> have to begin worrying about order of precedence.
>
>
>
> My point now is:
>
>
>
> Would the Murray's remark be still valid  if  we talk about a
> BNF grammar whose purpose is to write a parser to make available  just
> the expressions of the form  ( symbol := expression =E2=94=82 symbol
> = expression ) after discarding all the stuff on attributes and
> evaluation order? I am still  concerned, as I posted a year ago o so,
> with the =E2=80=98data dependency graph=E2=80=99  or =E2=80=98what we
> could call  =E2=80=98data dependency part of the parsing tree=E2=80=99.
>
>
>
> The underlying idea is to extract all the assignments (left and right
> sides)  in the code preventing the evaluation of the right hand sides.
> Wrapping the right hand sides in assignments  with
> =E2=80=98hold=E2=80=99  is unacceptable for my purpose and need.
>
>
>
> Counting on a BNF (affix)  Grammar, a simple way to extract the data
> dependency tree/graph would go like this:
>
>
>
> 1)      Save in plain text format the piece of code (in a notebook) that
> one needs to parse (all hidden code corresponding to the notebook
> interface would be dropped).
>
>
>
> 2)      Perform a first parsing step to drop all the elements mentioned
> or referenced by Murray (Hold and controls of order evaluation), leaving
> only the code corresponding to assignments and function definitions.
>
>
>
> 3)      Perform a second parsing step on the plain text obtained in the
> previous step, which will produce a set of assignments regardless they
> are delayed assignments or not.
>
>
>
> Maybe my ideas were clearer if I compare the above procedure with
> another, perhaps equivalent (?), method;  consisting in performing a
> separate (or concurrent) recursive descendent parsing on  all
> {DownValues, UpValues, OwnValues} for the symbols  in the piece of code
> we are interested in. In which case, the parsing trees got in each
> separate step  {DownValues, UpValues, OwnValues} will defined some valid
> form of data dependency graph for the whole piece of code.
>
>
>
> Then, with, say, Combinatorica, we would be able to explore and find
> important properties of the parsed code, easing up the task of: 1)
> Speeding up complex and tricky dynamic programs,  2) rewriting programs
> written in older (sometimes very old) Mathematica versions, and, 3) no
> less important, writing the final version of experimental programs
> written incrementally,  with step by step incremented  functionality,
> which typically result in something nearly unreadable.
>
>

[toc] | [prev] | [next] | [standalone]

#3254

On 6/22/2011 4:29 AM, Szabolcs Horv=E1t wrote:
> If you are looking to implement a Mathematica parser yourself, you might
> want to look at some earlier efforts first:
>
> http://omath.org/w/index.php?title=Main_Page#Developers
> http://stackoverflow.com/questions/1608380/parser-for-the-mathematica-syntax
> http://www.mathics.org/
>
> These pages contain links to several other projects (most dead by now).

I think you may miss the point :)   People who want to write a parser
for Mathematica typically want to write a parser WITHOUT REGARD TO THE
FACT THAT IT HAS ALREADY BEEN DONE.

That is, they subscribe to the belief that two weeks spent writing and
debugging can save five minutes searching on the web. maybe to learn??

And that only their own entirely pre-conceived version of the program in
their own precise framework (Java, C#, Linux, Lisp, Ruby, PHP, ecma, etc
could POSSIBLY be of interest).

A recently revised version of my (Lisp) mathematica parser and evaluator
is in http://www.cs.berkeley.edu/~fateman/lisp/mma4max/.
It was revised in order to read and execute Rubi.  The older and still
working versions 1.6 and 1.7 of mockmma are still around, but the
pattern matcher included there was not as nuanced as required.

If you spend some time writing a parser, you can learn a fair amount,
the first time. This is done by thousands of students in computer
science classes each year.  If you choose to do it on your own, you
should probably choose a language whose syntactic and lexical
description is crystal clear. That excludes Mathematica.

If you intend to write a parser for Mathematica not as a learning
experience, but as a practical tool,   (or as a free alternative to
Mathematica) then it seems to me natural to ask, why?  (I explain why I
wrote MockMMA in a paper published in the SIGSAM Bulletin.  Basically,
people who write Mathematica programs end up having to use some stuff
that I consider broken, like Mathematica arithmetic. Or slow.
Experimenting by using the same "user programs" but different support
might be of interest.  A few experiments by me and by others have used
this code. TILU,  some sourceforge project, some other stuff.)

RJF



>
> On 2011.05.25. 11:57, E. Martin-Serrano wrote:
>> On 2009 Murray Eisenberg posted the article linked below
>>
>>
>>
>> http://forums.wolfram.com/mathgroup/archive/2009/Apr/msg00232.html
>>
>>
>>
>> In which he wrote:
>>
>>
>>
>>>> It's not at all clear to me that a BNF would be of any great
>> use for Mathematica : after all, "everything is an expression" and so if
>> you avoid any of the "special input forms" such as =, :=, /@, {}, =
>> [[]],>>etc., along with prefix, infix, and postfix special forms, then
>> the grammar is utterly simple.
>>
>>
>>
>>>> The complexities arise from (1) Attributes, such as Hold, which do not
>> explicitly appear as part of the syntax one uses in entering expressions
>> but affect the evaluation; and (2) the special input>>forms, where you
>> have to begin worrying about order of precedence.
>>
>>
>>
>> My point now is:
>>
>>
>>
>> Would the Murray's remark be still valid  if  we talk about a
>> BNF grammar whose purpose is to write a parser to make available  just
>> the expressions of the form  ( symbol := expression =E2=94=82 symbol
>> = expression ) after discarding all the stuff on attributes and
>> evaluation order? I am still  concerned, as I posted a year ago o so,
>> with the =E2=80=98data dependency graph=E2=80=99  or =E2=80=98what we
>> could call  =E2=80=98data dependency part of the parsing tree==
E2=80=99.
>>
>>
>>
>> The underlying idea is to extract all the assignments (left and right
>> sides)  in the code preventing the evaluation of the right hand sides.
>> Wrapping the right hand sides in assignments  with
>> =E2=80=98hold=E2=80=99  is unacceptable for my purpose and=
 need.
>>
>>
>>
>> Counting on a BNF (affix)  Grammar, a simple way to extract the data
>> dependency tree/graph would go like this:
>>
>>
>>
>> 1)      Save in plain text format the piece of code (in a notebook) th=
at
>> one needs to parse (all hidden code corresponding to the notebook
>> interface would be dropped).
>>
>>
>>
>> 2)      Perform a first parsing step to drop all the elements mentione=
d
>> or referenced by Murray (Hold and controls of order evaluation), leavi=
ng
>> only the code corresponding to assignments and function definitions.
>>
>>
>>
>> 3)      Perform a second parsing step on the plain text obtained in th=
e
>> previous step, which will produce a set of assignments regardless they
>> are delayed assignments or not.
>>
>>
>>
>> Maybe my ideas were clearer if I compare the above procedure with
>> another, perhaps equivalent (?), method;  consisting in performing a
>> separate (or concurrent) recursive descendent parsing on  all
>> {DownValues, UpValues, OwnValues} for the symbols  in the piece of cod=
e
>> we are interested in. In which case, the parsing trees got in each
>> separate step  {DownValues, UpValues, OwnValues} will defined some val=
id
>> form of data dependency graph for the whole piece of code.
>>
>>
>>
>> Then, with, say, Combinatorica, we would be able to explore and find
>> important properties of the parsed code, easing up the task of: 1)
>> Speeding up complex and tricky dynamic programs,  2) rewriting program=
s
>> written in older (sometimes very old) Mathematica versions, and, 3) no
>> less important, writing the final version of experimental programs
>> written incrementally,  with step by step incremented  functionality,
>> which typically result in something nearly unreadable.
>>
>>
>
>

[toc] | [prev] | [next] | [standalone]

#3271

Thank you very much

-----Mensaje original-----
De: Szabolcs Horv=E1t [mailto:szhorvat@gmail.com]
Enviado el: mi=E9rcoles, 22 de junio de 2011 13:29
Para: mathgroup@smc.vnet.net
Asunto: Re: Again : Is there a BNF for Mathematica?


If you are looking to implement a Mathematica parser yourself, you might
want to look at some earlier efforts first:

http://omath.org/w/index.php?title=Main_Page#Developers
http://stackoverflow.com/questions/1608380/parser-for-the-mathematica-syntax
http://www.mathics.org/

These pages contain links to several other projects (most dead by now).

On 2011.05.25. 11:57, E. Martin-Serrano wrote:
> On 2009 Murray Eisenberg posted the article linked below
>
>
>
> http://forums.wolfram.com/mathgroup/archive/2009/Apr/msg00232.html
>
>
>
> In which he wrote:
>
>
>
>>> It's not at all clear to me that a BNF would be of any great
> use for Mathematica : after all, "everything is an expression" and so
> if you avoid any of the "special input forms" such as =, :=, /@, {}, > [[]],>>etc., along with prefix, infix, and postfix special forms, then 
> the grammar is utterly simple.
>
>
>
>>> The complexities arise from (1) Attributes, such as Hold, which do
>>> not
> explicitly appear as part of the syntax one uses in entering
> expressions but affect the evaluation; and (2) the special
> input>>forms, where you have to begin worrying about order of precedence.
>
>
>
> My point now is:
>
>
>
> Would the Murray's remark be still valid  if  we talk about a BNF
> grammar whose purpose is to write a parser to make available  just the 
> expressions of the form  ( symbol := expression =E2=94=82 symbol 
> expression ) after discarding all the stuff on attributes and
> evaluation order? I am still  concerned, as I posted a year ago o so,
> with the =E2=80=98data dependency graph=E2=80=99  or =E2=80=98what we
> could call  =E2=80=98data dependency part of the parsing tree=E2=80=99.
>
>
>
> The underlying idea is to extract all the assignments (left and right
> sides)  in the code preventing the evaluation of the right hand sides.
> Wrapping the right hand sides in assignments  with
> =E2=80=98hold=E2=80=99  is unacceptable for my purpose and =
need.
>
>
>
> Counting on a BNF (affix)  Grammar, a simple way to extract the data
> dependency tree/graph would go like this:
>
>
>
> 1)      Save in plain text format the piece of code (in a notebook) =
that
> one needs to parse (all hidden code corresponding to the notebook
> interface would be dropped).
>
>
>
> 2)      Perform a first parsing step to drop all the elements =
mentioned
> or referenced by Murray (Hold and controls of order evaluation),
> leaving only the code corresponding to assignments and function
definitions.
>
>
>
> 3)      Perform a second parsing step on the plain text obtained in =
the
> previous step, which will produce a set of assignments regardless they =

> are delayed assignments or not.
>
>
>
> Maybe my ideas were clearer if I compare the above procedure with
> another, perhaps equivalent (?), method;  consisting in performing a
> separate (or concurrent) recursive descendent parsing on  all
> {DownValues, UpValues, OwnValues} for the symbols  in the piece of
> code we are interested in. In which case, the parsing trees got in
> each separate step  {DownValues, UpValues, OwnValues} will defined
> some valid form of data dependency graph for the whole piece of code.
>
>
>
> Then, with, say, Combinatorica, we would be able to explore and find
> important properties of the parsed code, easing up the task of: 1)
> Speeding up complex and tricky dynamic programs,  2) rewriting
> programs written in older (sometimes very old) Mathematica versions,
> and, 3) no less important, writing the final version of experimental
> programs written incrementally,  with step by step incremented 
> functionality, which typically result in something nearly unreadable.
>
>

[toc] | [prev] | [standalone]

Back to top | Article view | comp.soft-sys.math.mathematica

csiph-web