[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

pl.comp.programming

Poprawnosc wyrazenia matematycznego

Adam Klobukowski

4/19/2007 4:33:00 PM

Witam

Musze napisaa funkcje sprawdzaj?c? poprawno?a wyra?enia matematycznego w
notacji infiksowej. O generowaniu parserów gramatyk wiem tyle ?e sie da,
a ?e sprawa jest pilna, podszed3em do tego od innej strony. Dziele
wyra?enie na tokeny, i w kolejno?ci od lewej do prawej, z uwzglednieniem
specjalnego przypadku pierwszego i ostatniego elementu, sprawdzam
nastepstwo tokenów. Tzn, sprawdzam jakiego rodzaju tokeny nastepuj? po
jakich. Tokeny dziele na operatory, operandy, funkcje, lewy nawias i
prawy nawias. Zak3adaj?c ?e poprawnie okre?li3em mo?liwe prawid3owe i
nieprawid3owe nastepstwa tokenów zastanawiam sie nad dwoma problemami:

1. Czy da sie skonstruowaa takie wyra?enie które przejdzie taki parser a
bedzie niepoprawne z matematycznego punktu widzenia
2. Czy da sie skonstruowaa takie wyra?enie które bedzie poprawne z
matematycznego punktu widzenia, a parser je odrzuci?


Stosuje nastepuj?ce zasady nastepstwa tokenów:

(Tabelka, marna troche ;)

X - nastepstwo niemo?liwe
O - nastepstwo mo?liwe

(tabelka nie bierze pod uwage specjalnego przypadku wnetrza funkcji,
które w moim przypadku s? tylko jednoargumentowe, nie bierze tez pod
uwage ostatniego tokenu)

\ token |o|o|f|l|p|
\ nastepujacy |p|p|u|e|r|
\ |e|e|n|w|a|
\ |r|r|k|y|w|
\ |a|a|c| |y|
\ |t|n|j|n| |
\ |o|d|a|a|n|
\ |r| | |w|a|
\ | | | |i|w|
\ | | | |a|i|
\ | | | |s|a|
\ | | | | |s|
\ | | | | | |
token \ | | | | | |
poprzedzaj?cy \| | | | | |
---------------+-+-+-+-+-+
operator |X|O|O|O|X|
---------------+-+-+-+-+-+
operand |O|X|X|X|O|
---------------+-+-+-+-+-+
funkcja |X|X|X|O|X|
---------------+-+-+-+-+-+
lewynawias |X|O|O|O|X|
---------------+-+-+-+-+-+
prawynawias |O|X|X|X|O|
---------------+-+-+-+-+-+
pierwszy token |X|O|O|O|X|
---------------+-+-+-+-+-+

No i rzecz jasna wyra?enia bez tokenów nie s? prawid3owe.

--
Semper Fidelis

Adam Klobukowski
adamklobukowski@gmail.com
15 Answers

Wojciech Mula

4/19/2007 5:30:00 PM

0

Adam Klobukowski wrote:
> Musze napisaa funkcje sprawdzaj?c? poprawno?a wyra?enia matematycznego w
> notacji infiksowej. O generowaniu parserów gramatyk wiem tyle ?e sie da,
> a ?e sprawa jest pilna, podszed3em do tego od innej strony. Dziele
> wyra?enie na tokeny, i w kolejno?ci od lewej do prawej, z uwzglednieniem
> specjalnego przypadku pierwszego i ostatniego elementu, sprawdzam
> nastepstwo tokenów. Tzn, sprawdzam jakiego rodzaju tokeny nastepuj? po
> jakich. Tokeny dziele na operatory, operandy, funkcje, lewy nawias i
> prawy nawias. Zak3adaj?c ?e poprawnie okre?li3em mo?liwe prawid3owe i
> nieprawid3owe nastepstwa tokenów zastanawiam sie nad dwoma problemami:

Powiniene? miea jeszcze operatory jednoarguementowe (przynajmniej minus,
plus niekoniecznie), bo nie przejdzie ani -5 ani 5 * -2.

w.

Adam Klobukowski

4/19/2007 5:50:00 PM

0

Wojciech Mu3a napisa3(a):
> Adam Klobukowski wrote:
>> Musze napisaa funkcje sprawdzaj?c? poprawno?a wyra?enia matematycznego
>> w notacji infiksowej. O generowaniu parserów gramatyk wiem tyle ?e sie
>> da, a ?e sprawa jest pilna, podszed3em do tego od innej strony. Dziele
>> wyra?enie na tokeny, i w kolejno?ci od lewej do prawej, z
>> uwzglednieniem specjalnego przypadku pierwszego i ostatniego elementu,
>> sprawdzam nastepstwo tokenów. Tzn, sprawdzam jakiego rodzaju tokeny
>> nastepuj? po jakich. Tokeny dziele na operatory, operandy, funkcje,
>> lewy nawias i prawy nawias. Zak3adaj?c ?e poprawnie okre?li3em mo?liwe
>> prawid3owe i nieprawid3owe nastepstwa tokenów zastanawiam sie nad
>> dwoma problemami:
>
> Powiniene? miea jeszcze operatory jednoarguementowe (przynajmniej minus,
> plus niekoniecznie), bo nie przejdzie ani -5 ani 5 * -2.

Zapomnia3em dodaa ze jednoargumentowy minus przerabiam na
dwuargumentowy, dodaj?c zero i nawiasy, czyli w podanych przyk3adach
by3oby to (0-5) i 5 * (0-2)

--
Semper Fidelis

Adam Klobukowski
adamklobukowski@gmail.com

Jacek Czerwinski

4/19/2007 6:19:00 PM

0

Dnia Thu, 19 Apr 2007 19:49:46 +0200, Adam Klobukowski napisa3(a):

> Wojciech Mu3a napisa3(a):
>> Adam Klobukowski wrote:
>>> Musze napisaa funkcje sprawdzaj?c? poprawno?a wyra?enia matematycznego
>>> w notacji infiksowej. O generowaniu parserów gramatyk wiem tyle ?e sie
>>> da, a ?e sprawa jest pilna, podszed3em do tego od innej strony.
Jak pilna to tym bardziej tzreba to postawia na nogach.
>>> Dziele
>>> wyra?enie na tokeny, i w kolejno?ci od lewej do prawej, z
>>> uwzglednieniem specjalnego przypadku pierwszego i ostatniego elementu,
>>> sprawdzam nastepstwo tokenów. Tzn, sprawdzam jakiego rodzaju tokeny
>>> nastepuj? po jakich.


>> Powiniene? miea jeszcze operatory jednoarguementowe (przynajmniej minus,
>> plus niekoniecznie), bo nie przejdzie ani -5 ani 5 * -2.
>
> Zapomnia3em dodaa ze jednoargumentowy minus przerabiam na
> dwuargumentowy, dodaj?c zero i nawiasy, czyli w podanych przyk3adach
> by3oby to (0-5) i 5 * (0-2)
Widzisz, przerabiasz .... sk?d wiesz, ?e przerabianiem nie sprowokujesz
b3edu. Jak uzupe3nisz np o jednoargumentowy bitowy negator (not) ?

Powspominajmy....
Najpierw robi3em analizator jezyka metod? "na upartego ma3ego jasia", co
moge sie pochwalic to ?e sie orobi3em po 3okcie (oczywi?cie projekt nie
ukonczony). Trwa3o to rok (do uznania pora?ki)

Potem, jak przyj?3em do wiadomo?ci teorie (i uzna3em ?e warto jej u?ya a
nie wynajdywaa ko3o) i zrobi3em super interpreter, wirtualn? maszynke i
debugger, uzupe3niony od zera napisanym edytorem pe3noekranowym.
W 2-3 miesi?ce. Pi?tka (szóstek wtedy nie by3o) z technik translacji w
po3owie semestru.

Przerabiasz zera (na bardziej okr?g3e mo?e), bedziesz przerabiaa co innego
a potem rzucisz w cholere.

Marcin 'Qrczak' Kowalczyk

4/19/2007 7:36:00 PM

0

Dnia 19-04-2007, czw o godzinie 18:32 +0200, Adam Klobukowski
napisal(a):

> Tzn, sprawdzam jakiego rodzaju tokeny nastepuja po jakich.

W ten sposób nie sprawdzisz, czy nawiasy sa do siebie dopasowane.

Proponuje zrobic normalny parser (np. metoda zejsc rekurencyjnych,
recursive descent, albo z uzyciem narzedzia do generowania parserów),
tylko nie budowac innego wyniku niz sprawdzenie poprawnosci.

--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.p...

Adam Klobukowski

4/19/2007 7:37:00 PM

0

Jacek Czerwinski napisa3(a):
> Dnia Thu, 19 Apr 2007 19:49:46 +0200, Adam Klobukowski napisa3(a):
>
>> Wojciech Mu3a napisa3(a):
>>> Adam Klobukowski wrote:
>>>> Musze napisaa funkcje sprawdzaj?c? poprawno?a wyra?enia matematycznego
>>>> w notacji infiksowej. O generowaniu parserów gramatyk wiem tyle ?e sie
>>>> da, a ?e sprawa jest pilna, podszed3em do tego od innej strony.
> Jak pilna to tym bardziej tzreba to postawia na nogach.
>>>> Dziele
>>>> wyra?enie na tokeny, i w kolejno?ci od lewej do prawej, z
>>>> uwzglednieniem specjalnego przypadku pierwszego i ostatniego elementu,
>>>> sprawdzam nastepstwo tokenów. Tzn, sprawdzam jakiego rodzaju tokeny
>>>> nastepuj? po jakich.
>
>
>>> Powiniene? miea jeszcze operatory jednoarguementowe (przynajmniej minus,
>>> plus niekoniecznie), bo nie przejdzie ani -5 ani 5 * -2.
>> Zapomnia3em dodaa ze jednoargumentowy minus przerabiam na
>> dwuargumentowy, dodaj?c zero i nawiasy, czyli w podanych przyk3adach
>> by3oby to (0-5) i 5 * (0-2)
> Widzisz, przerabiasz .... sk?d wiesz, ?e przerabianiem nie sprowokujesz
> b3edu. Jak uzupe3nisz np o jednoargumentowy bitowy negator (not) ?
>
> Powspominajmy....
> Najpierw robi3em analizator jezyka metod? "na upartego ma3ego jasia", co
> moge sie pochwalic to ?e sie orobi3em po 3okcie (oczywi?cie projekt nie
> ukonczony). Trwa3o to rok (do uznania pora?ki)

Dzieki bogu lista operatorów które musze obs3u?ya jest ?ci?le
ograniczona i okre?lona przez klienta :)

> Potem, jak przyj?3em do wiadomo?ci teorie (i uzna3em ?e warto jej u?ya a
> nie wynajdywaa ko3o) i zrobi3em super interpreter, wirtualn? maszynke i
> debugger, uzupe3niony od zera napisanym edytorem pe3noekranowym.
> W 2-3 miesi?ce. Pi?tka (szóstek wtedy nie by3o) z technik translacji w
> po3owie semestru.

Gratulacje :)

> Przerabiasz zera (na bardziej okr?g3e mo?e), bedziesz przerabiaa co innego
> a potem rzucisz w cholere.

Dzieki bogu mam dok3adnie okre?lone wymagania, tak ?e przerabiaa nic
wiecej nie bede usia3. Je?li klient zmieni wymagania to zap3aci
dodatkowo, tu mamy jasny uk3ad.

--
Semper Fidelis

Adam Klobukowski
adamklobukowski@gmail.com

Jacek Czerwinski

4/19/2007 8:56:00 PM

0

Dnia Thu, 19 Apr 2007 21:37:25 +0200, Adam Klobukowski napisa3(a):

> Dzieki bogu lista operatorów które musze obs3u?ya jest ?ci?le
> ograniczona
ale lista byków które mo?esz przy tym pope3nic jest nieskonczona.

> i okre?lona przez klienta :)
Któ? jest tym szcze?liwcem???


>> Potem, jak przyj?3em do wiadomo?ci teorie (i uzna3em ?e warto jej u?ya a
>> nie wynajdywaa ko3o) i zrobi3em super interpreter
> Gratulacje :)
Mam na my?li ?e jedynie mo?e sie udaa "po bo?emu"

>> Przerabiasz zera (na bardziej okr?g3e mo?e), bedziesz przerabiaa co innego
>> a potem rzucisz w cholere.
>
> Dzieki bogu mam dok3adnie okre?lone wymagania, tak ?e przerabiaa nic
> wiecej nie bede usia3.
Bedziesz musia3 jak dojdziesz do tego punktu, na razie tego nie wiesz.

>Je?li klient zmieni wymagania to zap3aci
> dodatkowo, tu mamy jasny uk3ad.

Chcia3e? powiedziea, ?e robisz komu? za kase na g3upawe zaliczenie ?
Nie potrafie tego zrozumiea, tylko tam bywaj? projekty o przydatno?ci zero.

Adam Klobukowski

4/20/2007 5:11:00 AM

0

Jacek Czerwinski napisa3(a):
> Dnia Thu, 19 Apr 2007 21:37:25 +0200, Adam Klobukowski napisa3(a):
>
>> Dzieki bogu lista operatorów które musze obs3u?ya jest ?ci?le
>> ograniczona
> ale lista byków które mo?esz przy tym pope3nic jest nieskonczona.
>
>> i okre?lona przez klienta :)
> Któ? jest tym szcze?liwcem???

Bardzo Powa?na Firma, niestety nie moge zdradzia.

>> Je?li klient zmieni wymagania to zap3aci
>> dodatkowo, tu mamy jasny uk3ad.
>
> Chcia3e? powiedziea, ?e robisz komu? za kase na g3upawe zaliczenie ?
> Nie potrafie tego zrozumiea, tylko tam bywaj? projekty o przydatno?ci zero.

Nie, to element wiekszego projektu.

--
Semper Fidelis

Adam Klobukowski
adamklobukowski@gmail.com

Pawel Kierski

4/20/2007 7:37:00 AM

0

Adam Klobukowski w wiadomo?ci <f08gdt$1u6$1@news.dialog.net.pl> pisze:
[...]
> Dzieki bogu lista operatorów które musze obs3u?ya jest ?ci?le
> ograniczona i okre?lona przez klienta :)

O co zak3ad, ?e sie zmieni? 8-)

[...]
> > Przerabiasz zera (na bardziej okr?g3e mo?e), bedziesz przerabiaa co innego
> > a potem rzucisz w cholere.
>
> Dzieki bogu mam dok3adnie okre?lone wymagania, tak ?e przerabiaa nic
> wiecej nie bede usia3. Je?li klient zmieni wymagania to zap3aci
> dodatkowo, tu mamy jasny uk3ad.

Pytanie, czy zap3aci za zamiany tyle, ?e Tobie bedzie sie op3acaa
przepisywaa wszystko od nowa, tym razem zgodnie z regu3ami sztuki?
Je?li teraz napiszesz porz?dnie, to twój zysk - w przypadku zmiany
ma3o sie ju? narobisz, a klient zap3aci. Je?li teraz nie zrobisz
porz?dnie, to klient bedzie chcia3 zap3acia, ale Ty mo?esz nie wyrobia
sie z wprowadzeniem tych zmian.

Robienie od razu dobrze to w d3u?szej perspektywie same zyski.

--
Pawe3 Kierski
news@pkierski.net
dodaj "[nomorespam]" w temacie je?li piszesz z domeny innej ni? .pl,
albo koniecznie chcesz obej?a moje filtry 8-)

Jacek Czerwinski

4/20/2007 8:34:00 AM

0

Dnia Fri, 20 Apr 2007 09:37:07 +0200, Pawe3 Kierski napisa3(a):

> Adam Klobukowski w wiadomo?ci <f08gdt$1u6$1@news.dialog.net.pl> pisze:
> [...]
>> Dzieki bogu lista operatorów które musze obs3u?ya jest ?ci?le
>> ograniczona i okre?lona przez klienta :)
>
> O co zak3ad, ?e sie zmieni? 8-)
>
> [...]
>>> Przerabiasz zera (na bardziej okr?g3e mo?e), bedziesz przerabiaa co innego
>>> a potem rzucisz w cholere.
>>
>> Dzieki bogu mam dok3adnie okre?lone wymagania, tak ?e przerabiaa nic
>> wiecej nie bede usia3. Je?li klient zmieni wymagania to zap3aci
>> dodatkowo, tu mamy jasny uk3ad.
>
> Pytanie, czy zap3aci za zamiany tyle, ?e Tobie bedzie sie op3acaa
> przepisywaa wszystko od nowa, tym razem zgodnie z regu3ami sztuki?
> Je?li teraz napiszesz porz?dnie, to twój zysk - w przypadku zmiany
> ma3o sie ju? narobisz, a klient zap3aci. Je?li teraz nie zrobisz
> porz?dnie, to klient bedzie chcia3 zap3acia, ale Ty mo?esz nie wyrobia
> sie z wprowadzeniem tych zmian.

Potem obie strony sie rozstaj?, pluj?c na siebie. I tak sie konczy
obustronna amatorszczyzna w idei i organizacji projektu.

mina86

4/21/2007 5:50:00 PM

0

Adam Klobukowski <adamklobukowski@gmail.com> writes:

> Musze napisaa funkcje sprawdzaj?c? poprawno?a wyra?enia matematycznego
> w notacji infiksowej. O generowaniu parserów gramatyk wiem tyle ?e sie
> da, a ?e sprawa jest pilna, podszed3em do tego od innej strony.

Skoro sprawa jest pilna to lepiej napisaa to korzystaj?c z bisona.
Nie jest to wcale trudny do opanowania program, a je?eli Twoja
aplikacja (funkcja, whatever) ma jedynie sprawdzaa poprawno?a
wyra?enia to wszystko staje sie jeszcze prostsze.

Gramatyke w ogóle mo?na upro?cia i zamiast rozpatrywaa wszystkie
operatory w gramatyce w lekserze ustalia podzia3 na 3 operatory:
jednoargumentowe, dwuargumentowe i takie, które mog? bya jedno- lub
dwuargumentowe (np. +, -). Np.:

#v+
%{
#include "heading.h"
int yyerror(char *s);
int yylex(void);
%}

%start input
%defines
%error-verbose

%token NUMBER, NAME
$token TWO_ARG_OPERATOR, ONE_ARG_OPERATOR, MIX_ARG_OPERATOR

%%
input : 'i'
| NAME '(' input ')'
| ONE_ARG_OPERATOR input
| MIX_ARG_OPERATOR input
| input TWO_ARG_OPERATOR input
| input MIX_ARG_OPERATOR input
| '(' input ')'
;

%%
int yyerror(char *message) {
fprintf("error: %s\n", message);
return 1;
}
#v-

Podejrzewam, ?e do powy?szego wystarczy podczepia lekser (funkcja
yylex) i ju? bedzie ?migaa.

--
Pozdrawiam _ _
.o. | Wasal Jasnie Oswieconej Pani Informatyki o' \,=./ `o
..o | Michal "mina86" Nazarewicz <mina86*tlen.pl> (o o)
ooo +---<jid:mina86*chrome.pl>---<tlen:mina86>----ooO--(_)--Ooo--