Recently I have developed a GPS NMEA Parser for an embedded system using the ATMega128 microcontroller, and decided to pack everything together as a GPS open source library for AVR Microcontrollers. The code is highly optimized to load the microprocessor as low as possible (both in terms of storage and CPU load), so the serial data is parsed as it gets in, without using redundant data structures or operations.
Project details available here: http://www.pocketmagic.net/?p=3821
Read the wiki on: https://github.com/radhoo/avr-nmea-gps-library/wiki